不含4-扇的平面图的全染色

摘要

设G=(V, E，F)表示顶点集为V，边集为E及面集为F的图.它的最大度与最小度用△与δ表示.图G的一个k-全染色是一个映射φ:V∪E→{1，…，k}，使得对任意相邻或相关联的元素u和v，满足φ(u)≠φ(v).若G有一个k-全染色，则说G是k-全可染的.图G的全色数是指最小的正整数k的值.显然，全色数至少为△+1.
　　关于图的全染色，在20世纪60年代，Vizing和Behzad就相互独立的提出:每个（简单）图G都是(△+2)-全可染的.这就是著名的全染色猜想，简称TCC.到目前为止，只有△=6的全染色猜想尚未得到解决.对于△=6平面图的全色数，吴建良和王应前等分别证明不含3-圈或不含4-圈时，TCC成立.侯建锋等证明不含5-圈或6-圈时，TCC成立.最近，Roussel给出这样的结论:若平面图的最大度为6，并且图中的每一点都不同时包含kv-圈，kv∈{3，4，5，6，7，8}，则这个平面图是8-全可染的.
　　对于平面图，多数情况下全色数是可以达到其下界(△+1)的.首先，Borodin等人证明了△≥11的平面图是(△+1)-全可染的;其次王维凡将前述结果改进到△=10，接着Kowalik等人又继续将结果改进到△=9.至于△≤8想要证明同样整洁的结果似乎非常困难.考虑△=8的平面图的9-全可染性，侯建锋等人证明了△≥8且无4-圈的平面图是9-全可染的.此后，无4-圈的这个附加条件不断被减弱为:无5-圈或无6-圈;无相交1-扇;无2-扇;无3-扇等.
　　本文在前人已有的经验基础上，主要围绕TCC，在平面图的全染色猜想中，通过研究极小反例，构建新的可约构型，运用权转移的方法证明了:
　　(1)若G是△=6且不含4-扇的平面图，则G是8-全可染的.
　　(2)若G是△=8且不含4-扇的平面图，则G是9-全可染的.
　　这里的4-扇是指交于一点的4个相继的3-面，类似地，k个相继的3-面称为k-扇.这两个结果改进了若干同类型的相关结果.

目录

摘要

1 绪论

1．1 基本概念

1．2 全染色问题的研究概况

1．3 本文的主要结果

2 Δ=6且不含4-扇的平面图的全染色

2．1 可约构型

2．2 定理2．1的证明

3 Δ=8且不含4-扇的平面图的全染色

3．1 可约构型

3．2 定理3．1的证明

参考文献

在学期间的研究成果及发表的论文

致谢

声明

浙江师范大学学位论文诚信承诺书