摘要: 用G=(V,E)表示顶点集为V，边集为E的图，而图的最大度，最小度分别用△，δ表示.若G是平面图，常用F表示它的面集.若V∪E中的元素能用k种颜色进行染色，使得任意两个相邻或相关联的元素染有不同的颜色,则称G是k-全可染的.用x11(G)来表示图G的全色数，即... 展开 用G=(V,E)表示顶点集为V，边集为E的图，而图的最大度，最小度分别用△，δ表示.若G是平面图，常用F表示它的面集.若V∪E中的元素能用k种颜色进行染色，使得任意两个相邻或相关联的元素染有不同的颜色,则称G是k-全可染的.用x11(G)来表示图G的全色数，即使得G有k-全染色的最小的正整数k.显然，对每个图进行全染色，至少需要△(G)+1个色.图G的一个正常顶点k-染色是指一个映射φ:V→{1，…,k}，使得对任意uv∈E(G)，满足φ(u)≠φ(v).若G有k-染色，则称G是k-可染的.用x(G)来表示图G的点色数，即使得G有k-染色的最小的正整数k.现在给G的每个顶点v分配一个颜色集合L(v)，则称L={L(v)/v∈V}是G的一个色列表.若对(V)v∈G，都能从其相应的色列表L(v)中选取一个颜色φ(v)染给υ，使得(V)uv∈E(G)，有φ(u)≠φ(v)，则称G是L-可染的.若G对任意一个满足|L(v)|≥k的色列表L,G都是L-可染的，则称G是k-列表可染的，也称G是k-可选择的.用ch(G)来表示图G的选择数，即使得G是k-可选择的最小的正整数k.图G的一个线性k-染色是指G的一个正常顶点k-染色满足任意两种颜色的点导出子图是点不交的路的并.用1c(G)来表示图G的线性色数，即使得G有一个线性k-染色的最小的正整数k. 本文在前人的工作基础上，主要研究了图的这三种染色问题. 论文分为四章，第一章主要是对本学位论文所涉及的问题，背景，定义及全染色，3-列表染色，线性染色的研究现状进行了一个综述. 第二章主要研究了平面图的全染色的问题.关于图的全染色,有以下著名的猜想(Total Coloring Conjecture):对任意图G，x″(G)≤△(G)+2.猜想主要由Vizing和Behzad等人独立提出，简称TCC，但是随着研究的深入，人们发现许多图不仅仅是满足TCC的.更进一步地，很多图的全色数是可以取到下界△(G)+1的.对此，王应前老师提出了平面图上的全染色猜想:对每个△(G)≥4的平面图G，x″(G)=△(G)+1.本章主要研究了最大度至少为6且不含带弦5圈和带弦6圈的平面图的全染色. 第三章主要研究了平面图的3-列表染色问题.关于图的3-列表染色，是在3-染色的基础上展开研究的.Steinberge猜想指出不含4，5圈的平面图是3-可染的.一个自然的问题就是不含4，5圈的平面图是否是3-列表可染的呢？对此，Vogit给出了不含4，5圈但非3-列表可染的例子.Montassier提出猜想:不含4，5,6圈的平面图是3-可选择的.本章主要证明了不含4，5，8，10圈的平面图是3-列表可染的以及不含4，6，9，10圈的平面图是3-列表可染. 第四章研究了图的线性染色问题.关于图的线性染色问题，显然有1c(G)≥[△/2]+1.Cranston和Yu猜想:对每个mad(G)＜3的图，有1c(G)≤[△/2]+2.本章基于这个猜想，研究了mad(G)＜2.8的图的线性染色问题. 收起