图的若干染色问题研究

论文摘要

用G=（V,E）表示顶点集为V.边集为E的图,而图的最大度,最小度分别用△,δ表示.若G是平面图.常用F表示它的面集.若V∪E中的元素能用k种颜色进行染色,使得任意两个相邻或相关联的元素染有不同的颜色：则称G是k-全可染的.用x”（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∈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-染色满足任意两种颜色的点导出子图是点不交的路的并.用lc（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-列表可染.第四章研究了图的线性染色问题.关于图的线性染色问题,显然有lc(G≥[△/2]+1. Cranston和Yu猜想：对每个mad（G）<3的图,有lc（G）≤[△/2]+2本章基于这个猜想,研究了mad（G）<2.8的图的线性染色问题.

论文目录

• 摘要
• ABSTRACT
• 目录
• 1 绪论
• 1.1 基本概念
• 1.2 全染色.（?）表染色和线性染色问题的研究概况
• 1.3 本文的主要结果
• 2 平面图的全染色
• 2.1 Δ≥6且不含带弦5-圈和带弦6-圈的平面图的全染色
• 3 平面图的3 -可选择性
• 3.1 不含4.5.8.10圈的平面图是3-可选择的
• 3.2 不含4.6.9.10圈的平面图是3-可选择的
• 4 图的线性染色
• 4.1 稀疏图的线性染色
• 参考文献
• 在学期间的研究成果及发表的论文
• 致谢