唯一顶点着色、唯一列表着色的整体结构与其着色参数的关系的讨论

摘要

这篇论文是一篇关于顶点着色综述性的文章。 对图G(V,E)的一种着色是一个标号映射c:V→S,使得(∨) VW∈E(G),c(v)≠c(w).一个k-colouring是在顶点集V上的一个由k个色类构成的划分,使得在同一色类中的点不相邻。使得图G存在k-colouring c:V→{1,…,k}的最小的正整数k称为G的chromatic number,记为x(G)。如果图G的任何k-colouring产生的色类划分相同,我们称G是uniquely vertex k-colourable(or a k-UCG)。如果对图G的任何list assignment(￡)={L(v):v∈V(G)}且|L(v)|=k,都能选择到G的着色。我们称G是k-list-colourable,或k-choosable,使得G是k-choosable最小的正整数k称为G的list chromatic number或choosability,记为ch(G)或x1(G)。 第一章主要介绍了关于顶点着色的基本概念,一些着色参数的基本性质,简略地讨论了着色参数与图的结构的关系,最后一节是研究的进展和本文的主要结论。 第二章找出例图使得ch(G)>x(G)或ch(G)=x(a),介绍了Woodal l,Gravier和Maffray关于相等的猜测。给出了使得G是n-choosable的与kernel有关的充分条件,而且进一步指出线图是可解的当且仅当它是完美的,二部多重图的线图是可解的。 第三章介绍了与n-choosable图不同的uniquely list colourable图的性质,主要介绍了uniquely 2-list colourable图的性质,一个连通图G是uniquely 2-list colourable当且仅当它至少有一块(block)既不是圈,不是完全图,也不是完全二部图。一个连通图G是uniquely 2-list colourable当且仅当它至少有一块(block)既不是圈,不是完全图,也不是完全二部图。图G是uniquely 2-list colourable当且仅当它是t=max{3,x(G)}的uniquely(2,t)-list colourable。 在第四章的第一节,我们研究构造无Kk的k-UCG时,计算参数∧(G)的值。首先找出具体的图说明无Kk的k-UCG的存在性,以此为基础用逼迫的办法构造k-UCG,而不增加团数,给出了计算∧(G)的公式。在第二节用uniquely list eolourable图(G,(￡)t)与团Kt构造t-UCG ～HG,φ,t,来计算固定集的最小值φ0(G),给出了Xφ(G)与其它着色参数的不严格的不等式,而且计算出了圈Cn,路径Pn和彼得松图P的xφ(G)。

目录

文摘

英文文摘

声明

第一章引 言

§1.1顶点着色的基本概念和基本知识

§1.2着色参数χ(G)的一些性质。

§1.3着色参数与图的整体结构的关系

§1.4本文涉及到的主要结论

第二章图的列表着色的若干问题

§2.1列表着色的简介

§2.2列表着色概念的延拓

第三章唯一列表可着色图

§3.1唯一列表可着色图的概念与性质

§3.2唯一2列表可着色图的性质

§3.3唯一2列表可着色图与总色数t的关系

第四章t-UCG的若干问题

§4.1不含Kn的t-UCG的参数人(G)的讨论

§4.2嵌入团K1的t-UCG与唯一列表可着色图之间的关系以及参数χφ(G)的讨论

结束语

参考文献