论文部分内容阅读
本文主要研究了平面图的一类推广的边染色问题:邻接点区分边染色,所讨论的图均为简单图. 设φ:E(G)→{1,2,…,k}是从G的边集构成的集合E(G)到自然数集的一个映射,如果对任意相邻接的两个元素x,y∈E(G)均有φ(x)≠φ(y),则称φ是G的一个正常边染色. 邻接点区分染色是边染色的一中推广,这种染色对于图G的边可选用的颜色有一定的限制.我们用Cφ(v)来表示与顶点v相关联的边的颜色集合,即Cφ(v)={φ(uv)|uv∈E(G)}.如果φ是图G的一个正常边染色,同时对任意一对邻接点u和v满足Cφ(u)≠Cφ(v),则称φ是图G的一个邻接点区分边染色.我们用Xavd(G)来表示图G的邻接点区分边染色数,它是使得图G是邻接点区分边可染的最小的正整数k,即Xavd(G)=min{k|G是k-邻接点区分边可染的}. Zhang等人[22]完全解决了路,圈,树,完全图和完全二部图的邻接点区分边染色问题,并提出一个重要猜想:如果图G是一个顶点数至少是3的连通图,且不是长为5的圈,那么图G的邻接点区分边染色数将不会超过△(G)+2.Balister, Hatami,卜月华,王维凡等人通过对图的最大平均度,可平面图的围长,最大度等的讨论,对这一猜想进行了一系列研究.其中卜月华,王维儿等人证明该猜想对围长至少为6的平面图是正确的.在本文中,我们将在卜月华,王维凡等人关于围长至少为6的平面图的一些结论的基础上,进一步把围长缩小至5,得到如下结论: 若图G是一个没有孤立边的平面图,且G的围长g(G)不小于5,则Xavd(G)≤△(G)+4. 这是一个几乎紧的界,因为Xavd(C5)=△(C5)+3. 本文第一章主要介绍一下基本概念和已有结论,第二章给出了围长大于等于5,没有孤立边的平面图的邻接点区分染色数,第三章给出了一些可以进一步研究的问题.