论文部分内容阅读
若可以将图G画在一个平面上且使得它的边仅在顶点处相交,那么称这样的图G为平面图.本文所描述的图都是简单的,有限的平面图.图G的k-2-距离染色是指一个映射ψ:V→{1,…,k},满足若0< dG(u,v)≤2,则有ψ(u)≠ψ(v).图G的2-距离色数x2(G)=min{k|G有一个k-2-距离染色}.若给G的每一个顶点都指定可用色集L(v),|L(v)|≥k,则称L={L(v)|v∈V(G)}是G的一个的列表配置.若对于G的任何一个大小为k的列表配置L,G都是L-2-距离可染的,那么称G是k-2-距离列表可染的.G的2-距离列表色数是指使得G是k-2-距离列表可染的最小正整数k,记之为xl2(G). 平面图的2-距离染色问题,最早由Wegner在1977年发表文献并提出了得到许多数学家学者关注的猜想:对平面图G,(1)若△(G)=3,则x2(G)≤7;(2)若4≤△(G)≤7,则x2(G)≤△(G)+5;(3)若△(G)≥8,则x2(G)≤([)3/2△(G)」+1.Wegner的猜想目前为止还待研究.而对于不含短圈的平面图,能证明存在紧的2-距离色数的上界.王维凡和蔡雷镇曾提出问题:对于不含4-圈的平面图G,求满足x2(G)≤△(G)+t的t的最小值. 本论文主要研究了不含短圈的平面图的2-距离染色及2-距离列表染色.第一部分主要介绍了一些相关的概念,并综述了2-距离染色以及2-距离列表染色的研究现状和一些主要存在的问题.第二部分主要讨论围长大于等于5的平面图以及围长大于等于6的平面图的2-距离列表染色.第三部分对不含4,5-圈的平面图的2-距离列表染色数进行了讨论.第四部分主要讨论了不含4-圈的平面图的2-距离染色.