论文部分内容阅读
令G=(V,E)是一个有限简单平面图,用△(G)和g(G)分别表示图G的最大度和围长.我们把不含孤立边的图称为正常图.设φ是G的一个正常边染色,满足任意相邻的两个顶点有不同的色集合,则称φ是G的邻点可区别边染色(简记avd-染色).图G的邻点可区别边色数是指使得G有一个邻点可区别边染色所需的最少颜色数,记作χa’(G).2002年,Zhang等人提出邻点可区别边染色,并提出猜想:设图G是简单连通图且G≠C5,则χa’(G)≤△(G)+2.Hatami在2005年用概率的方法证明了当正常图G的△(G)≥ 1020时,有χa’(G)≤△(G)+300.Balister等人在2007年验证了所有的二部图和△(G)≤ 3的图满足猜想,也证明了对任意正常图G有χa’(G)≤△(G)+O(log k),其中k表示图G的点色数.Yan等人在2014年证明了若图G是g(G)≥5且G≠C5的平面图,则χa’(G)≤△(G)+2.Huang等人在2015年证明了若G是无3-圈且△(G)≥ 12的平面图,则xa’(G)≤ △(G)+1.本论文是在前人研究的基础上,进一步探讨图的邻点可区别边色数,全文主要分成以下三部分:第一章,我们主要介绍了本文用到的一些定义和基本概念,并简述了相关研究领域的研究现状和本文主要的研究成果.第二、三章,我们研究了无短圈的平面图的邻点可区别边色数.我们先研究极小反例图的结构性质,再用权转移方法证明极小反例不存在,证明了以下两个结果:(1)设G是无4-圈的平面图,且G不含K2作为子图,则χa’(G)≤max{9,Δ(G)+1}.(2)设G是无3-圈的平面图,且G不含K2作为子图.(2.1)令 T(G)=max{10,△(G)+1},则χa’(G)≤ T(G).(2.2)如果△(G)≥ 10,则χa’(G)=△(G)+1当且仅当图G包含两个相邻的△(G)-点.第四章,我们用类似的方法研究了有大围长的平面图的邻点可区别边色数,证明了以下结果:(3)设G是不含K2作为子图的平面图且g(G)≥ 5,则χa’(G)≤max{8,Δ(G)+1}.