论文部分内容阅读
用G=(V,E)表示顶点集为V,边集为E的图,而图的面集,最大度,最小度分别用F,△,δ表示.若V∪ E中的元素能用k种颜色进行染色,使得任意两个相邻或相关联的元素染有不同的颜色,则称G是K-全可染的.图G的一个全色列表是一个颜色集合簇L,对G的每个元素x∈V ∪ E都配一个颜色集合L(x).若对每一个满足|L(x)|=k,x∈V∪ E的L,G都是L-全可染的,则称G是k-全可选的.图G的一个正常k-顶点染色是指一个映射φ:V→{1,…,k},使得对任意uv∈E(G),满足φ(u)≠φ(v).
关于图的全可选和边可选,有以下著名的猜想(List Coloring Conjecture):对任意图G,(a))xl(G)=x(G);(b)x"l(G)=x"(G).猜想主要由Vizing和Borodin等人独立提出.关于平面图的3-染色问题,最著名的是Steinberg猜想:不含4,5-圈的平面图是3-可染的.人们的一系列研究主要围绕这两个问题展开,通过多年研究人员的不断改进,现已有一定的进展.
本文在前人的工作基础上,围绕上述猜想和问题,在平面图的全可选中,主要运用Discharging方法证明了:
(1)△≥8且不含相交三角形的平面图G是(△+1)-全可选的;
(2)△≥9且不含相邻三角形的平面图G是(△+1)-全可选的.
在平面图的3-染色中,运用延拓性引理,坏圈,新好路的定义和Discharging等方法,证明了:
(3)不含带弦4至9-圈的平面图G是3-可染的.