论文部分内容阅读
本文考虑的图G是有限,简单(无环,无重边),无向图.如果图G=(V,E)能被嵌入到一个平面使得边仅在端点处相交,称它是可平面的.可平面图在平面内的一个嵌入叫平面图.设G=(V,E)是顶点集为V,边集为E的平面图.图G的一个k-染色是一个映射λ:V→{1,2,…,k}满足任意uv∈E使得λ(u)≠λ(v).若图G存在一个k-染色,则称G是k-可染的. 在定义图G的k-染色λ时,其中集合{1,2,…,k}称为图G每个顶点的可用色集合.若允许可用色集合多样化,就得到列表染色的概念.更准确地说,若(V)v∈V,都配置一个列表可用色L(v),则L={L(v)|v∈V}被称为图G的一个染色列表配置.如果(V)v∈V都有|L(v)|=k,则L被称为图G的一个列表配置.若(V)k-列表配置L,都能从L(v)中选择一个颜色v,使得对任意边xy∈E满足λ(x)≠λ(y),则称图G是列表k-可染的,或者称图G是k-可选的.显然对每个v∈V可以选择列表L(v)={1,2,…,k}.因此,若图G是k-可选的,一定是k-可染的.反之则不然. Erd(o)s et al.[1]刻画了所有的2-可选图;Thomassen[2]证明了可平面图的5-可选性;Voigt[3]证明了存在一个非4-可选的平面图;Gutner[4]证明确定一个平面图是否为3-或4-可选的问题是NP-hard的.所以,证明一个平面图是3-或4-可选的充分条件变得十分有意义.基于这些猜想和问题,诸多学者对上述问题展开研究并取得了一系列的成果. 本文分三章展开,主要围绕猜想及相关问题展开研究,所得结论改进了现有的一些结果.第一章介绍了本论文所涉及的相关定义与符号,并做了一个关于正常列表染色研究现状的综述;第二章介绍不含三角4-圈的平面图是4-可选的;第三章介绍不含短圈且限制三角形距离的平面图是3-可选的.