平面图的3列表染色及FM分解

论文摘要

图G的一个正常k染色是指一个映射φ：V→{1,…,k},使得对任意uv∈E（G）,有φ（u）≠φ（v）.若图G有一个正常k染色,则称图G是k可染的.设G=（V, E）,给G的每个顶点v∈V（G）分配一个可用色集合L（v）（不同的点可以分配相同或不同的可用色集合）,则得到G的一张色列表L={L（v）|v∈V}.若对任意的v∈V,都能从相对应的色列表L（v）中选取一个颜色染给v,使得G有一个正常染色,则称G是L可染的.若对G的任意一张满足|L（v）|≥k（（?） v∈V）的色列表L,G都是L可染的,则称G是k列表可染的.1996年,Gutner证明确定一个平面图是3列表可染,或4列表可染的问题是NP困难的.因此,寻找平面图是3或4列表可染的充分条件成为图的染色理论中的一个重要研究课题.2006年,Montassier等人证明了不含4,5,6圈且三角形的距离至少为3的平面图是3列表可染的；2008年,Montassier等人证明了6-圈的距离至少为3的平面图是3列表可染的.本文在前人的工作基础上,综合运用Discharge和结构分析等方法,得到了一个更好的结果：（1）每一个不含相交i圈与j圈,4≤i≤j≤6,且三角形与5-圈的距离至少为3的平面图是3列表可染的.2005年,Lam等人证明了没有3,5,6圈的平面图是3列表可染的.2008年,Zhang等人证明了没有5,6,7圈且三角形距离至少为3的平面图和没有5,6,8圈且三角形距离至少为2的平面图都是3列表可染的；2008年,Montassier等人证明了7-圈的距离至少为2的平面图是3列表可染的.本文在前人的工作基础上,综合运用Discharge和结构分析等方法,得到了一个更好的结果：（2）相邻两圈的长度之和至少为11且三角形距离至少为2的平面图是3列表可染的.1995年,Thomassen证明了围长为5的平面图是3列表可染的；2009年,Li证明了没有3圈且4圈不与4,5圈相交的平面图是3列表可染的.本文在前人的工作基础上,综合运用色延拓和归纳等方法,得到了一个更好的结果：（3）没有三角形且4圈不与4,5圈相邻的平面图是3列表可染的.图G的分解是指把图G分解成图G的一系列子图且图G的每条边出现且只出现在一个子图内.图G的FM分解是指把图G分解成两个子图,一个为森林（Forest）,另一个为匹配（Matching）.2002年,He等人证明了围长至少为11的平面图可以分解成一个森林和一个匹配.2004年,Kleitman等人证明了围长至少为10的平面图可以分解成一个森林和一个匹配.2008年,Borodin等人证明了围长至少为9的平面图可以分解成一个森林和一个匹配,并在文中提出对于围长至少为8的平面图是否可以分解成一个森林和一个匹配仍旧是一个公开且有趣的问题.围绕上述问题,本文在前人研究的基础上,运用粘点和Discharge等方法,继续研究平面图的FM分解问题,证明了：（4）围长至少为8的平面图可以分解成一个森林和一个匹配.

论文目录

• 摘要
• ABSTRACT
• 目录
• 1 绪论
• 1.1 基本概念
• 1.2 平面图的3列表染色和FM分解的研究状况
• 1.3 本文的主要结果
• 2 平面图的3列表染色
• 2.1 三角形距离至少为3的平面图的3列表染色
• 2.2 三角形距离至少为2的平面图的3列表染色
• 2.3 没有三角形的平面图的3列表染色
• 3 平面图的FM分解
• 3.1 围长至少为8的平面图的FM分解
• 参考文献
• 攻读学位期间取得的研究成果
• 致谢