论文部分内容阅读
给定一个平面图G=(V, E)，它的顶点集，边集，面集，最大度和最小度分别用V，E，F，△和δ表示.若V∪E中的元素能够用k种颜色进行染色，使得任意两个相邻或相关联的元素都染有不同的颜色，则称图G有一个正常的k-全染色，也称图G是k-全可染的.使得图G是正常k-全染色的最小的正整数k叫做图G的全色数.显然，全色数至少为△+1.图G的一个全色列表是一个颜色集合簇L，对图G中的每个元素x∈V∪E都配有一个颜色集合L(x).若对每一个满足|L(x)|=k，x∈V∪E的L,图G都是L-全可染的，则称图G是k-全可选的.
对于图的全染色，早在20世纪60年代，Vizing和Behzad就分别独立的提出了全染色猜想:任意的简单图G都是(△+2)-全可染的.到目前为止，只有△=6的平面图是否是8-全可染的问题尚未解决.关于图的全可选和边可选，有以下著名的猜想(List Coloring Conjecture):对任意图G，(a)xl(G)=x(G);(b)xl"(G)=x"(G).
本文在前人的工作基础上，围绕着上述猜想和问题，在平面图的全可染和全可选中，主要运用Discharging方法证明了:
(1)3-圈和6-圈不相邻的平面图G是(△+2)-全可染的.
(2)△≥7且不含相邻4-(-)圈的平面图G是(△+1)-全可选的;△≥8且3-圈和5-圈不相邻的平面图G是(△+1)-全可选的;△≥6且3-圈和5-圈不相邻的平面图G是(△+2)-全可选的;
(3)△≥9且不含相邻4-圈的平面图G是(△+1)-全可选的.