摘要: 一个有序对G=(V,E)称为一个无向图,其中V是一个有限集合,E是V中的不同元素的无序对的集合.V中的元素叫做图G的顶点,E中的元素叫做图G的边.通常用V(G),E(G)分别表示图G的顶点集合与边集合.没有重边和环的图叫做简单图. 图G的一个k-边染色是一个映射... 展开 一个有序对G=(V,E)称为一个无向图,其中V是一个有限集合,E是V中的不同元素的无序对的集合.V中的元素叫做图G的顶点,E中的元素叫做图G的边.通常用V(G),E(G)分别表示图G的顶点集合与边集合.没有重边和环的图叫做简单图. 图G的一个k-边染色是一个映射φ:E(G)→{1,2,…,k},其中k是整数.若映射φ还满足对于G中的每一对相邻边e和e′,有φ(e)≠φ(e′),则称这个k-边染色是正常的.如果G有一个正常的k-边染色,则称G是k-边可染的.G的边色数x′(G)是使得G是k-边可染的最小的整数,称L为图G的一个边列表,如果它给每条边e∈G,一个颜色集合L(e),若有一个正常的边染色φ,使得每一条边e满足φ(e)∈L(e)则称G是L-边可染的,或称φ是G的一个L-边染色.如果对任意表L和每条边e∈E(G),都有｜L(e)｜≥k,且G是L-边可染的,则称G是k-边可选的.G的边列表色数x′l(G)是使得G是k-边可选择的最小的非负整数k.类似地可定义单独染顶点和同时染顶点和边的G的点列表色数xl(G)和全列表色数x"l(G).由定义可直接得到x′'(G)≥x′(G)≥△(G)和x"l(G)≥x"(G)≥△(G)+1. 如果图G的一个正常顶点染色c满足染任意两种颜色的顶点集合导出的子图是一个线性森林,即一些点不交的路的并,则称这个正常点染色c为图G的线性染色.图G的线性色数,是指图G的所有线性染色中使用的最少颜色的个数,用lc(G)表示. 本文主要讨论平面图的边列表染色和线性染色问题.对前人的一些研究结果进行改进和补充. 在第一章中,给出本文所用到的基本概念,介绍相关领域的背景和研究现状,呈现本文的主要结果. 第二章中,主要证明了关于平面图的边列表染色的研究结果:最大度为6且不含4-圈和7-圈的平面图是△-边可选的,(△+1)-全可选的；最大度为5且不含4,6,8-圈的平面图是△-边可选的,(△+1)-全可选的. 第三章中证明了关于平面图的线性染色的研究结果:设G是一个平面图,若G满足下面条件之一,则lc(G)=「△(G)／2()+1 (1)△(G)≥11且g(G)≥7 (2)△(G)≥5且g(G)≥9 收起