论文部分内容阅读
图G的正常k边染色是指存在一个映射φ:E(G)→{1,2,…,k},使得相邻的边e和e满足φ(e)≠φ(e).令Cφ(v)表示与点v相关联的边的颜色所构成的颜色集合,即Cφ(v)={φ(uv)|uv∈E(G)}.图G的距离为2的点可区别边染色是指,G的一个正常边染色满足对任意的两个距离为2的顶点u和v,都有Cφ(u)≠Cφ(v).图G的距离为2的点可区别边色数xd2(G)是指G有一个距离为2的点可区别k-边染色的最小k值. 图的距离为2的点可区别边染色是r-强边染色的一种特殊情形.图的r-强边染色是由Akbari等人和Zhang等人在2006年分别独立提出的.设r≥1是一个整数,图G的r-强边色数xs(G,r)是指G的一个正常边染色φ满足对任意两个顶点u和v,若d(u,v)≤r,都有Cφ(u)≠Cφ(v)的最小颜色数. 若r=1,则xs(G,1)=xa(G),xa(G)被称为邻点可区别边色数.邻点可区别边染色最早是由Zhang,Liu和Wang在2002年提出的,他们猜想:若G是一个|V(G)|≥6的连通图,则有xa(G)≤△+2.Balister等人证明了猜想对二部图和最大度不大于3的图是成立的.Hatami运用概率方法证明了对每一个△>1020的图G,都有xa(G)≤△+300.Akbari,Bidkhori和Nosrati证明了对每一个图G,都有xa(G)≤3△.随后Wang等人将这个界进行了改进,证明了对任意的图G,xa(G)≤2.5△. 本学位论文主要研究了图的距离为2的点可区别边染色问题,共分四章. 在第一章中,介绍了基本概念和相关领域的研究现状,并且呈现了本文的主要结果. 在第二章中,研究了特殊图类的距离为2的点可区别边染色,确定了一些简单图类、单圈图以及两类积图的距离为2的点可区别边色数. 在第三章中,研究了哈林图的距离为2的点可区别边染色,证明了哈林图的距离为2的点可区别边色数的上界是△+2. 在第四章中,研究了外平面图的距离为2的点可区别边染色,先证明了外平面图的距离为2的点可区别边色数的上界是2△,随后证明将上界改进到了△+8,最后证明了一类特殊外平面图的距离为2的点可区别边色数的上界是△+2.