图的邻点可区别全染色与局部反魔幻标号

发布时间：2020-06-17 04:43

【摘要】：图的染色与标号问题是图论中的重要分支,其研究历史久远.作为图论发展的先导之一:四色定理,就是典型的染色问题.一直以来,图的染色与标号问题备受关注,它们不仅在图论上扮演重要角色,而且在社会科学、生命科学等方面都有着广泛应用.图的染色与标号本质上都是从图的点集或边集到实数集的映射.我们首先研究的是平面图的邻点可区别全染色问题.图G的k-全染色是指用集合[k]中的颜色(即元素)对图的点和边同时进行染色,使得相邻的点、相邻的边以及相关联的点和边都染不同颜色.对于G的一个k-全染色φ,我们用C(v)来表示由点v以及v的所有关联边的颜色构成的集合.我们称点v和点u是冲突的,如果两点相邻且Cφ(v)=Cφ(u).如果G中任意两个邻点都不冲突,则称k-全染色φ是邻点可区别的.我们将能够使得G具有邻点可区别全染色的最小的颜色数k称为图G的邻点可区别全色数,记作χ"a(G).2005年,Zhang等人首次提出这种染色并猜想:对于至少有两个点的连通图G,均有χ"a(G)≤△(G)+ 3.Cheng等人已经证明对于最大度至少为10的平面图,上述猜想成立.本文在第二章中证明了对于最大度△(G)≥9的平面图G,有χ"a(G)≤ △(G)+ 3,改进了已有的结果,从而推动猜想的解决.进一步,对于最大度△(G)≥ 10的平面图G,我们得到了更好的上界,即χ"a(G)≤ △(G)+ 2.在第三章中,我们主要考虑图的局部k-反魔幻定向.设D是图G的一个定向且G的边数为m,D的局部k-反魔幻标号是指这样一个映射:将D的边集映射到[m + k],使得任意两条边的标号(即像)不同,且任意两个邻点的点和互异,其中点和是指该点所有入边的标号之和减去所有出边的标号之和.如果D有局部k-反魔幻标号,那么就称D是图G的一个局部k-反魔幻定向.当k = 0时,简称局部k-反魔幻标号(定向)为局部反魔幻标号(定向).之所以考虑该问题,是受著名的反魔幻标号猜想和1-2-3猜想的启发.反魔幻标号猜想自1990年被提出以来受到广泛关注,但至今仍未完全解决,其难度在于不仅要求任意两条边的标号互异,而且任意两个点所关联的边的标号之和也要不同.而1-2-3猜想只要求区分邻点,受此启发,我们开始研究图的局部反魔幻标号,进而推广到有向图.Chang等人猜想:每一个连通图都存在一个局部反魔幻定向.本文中,我们证明了每一个d-退化图都存在一个局部(d + 2)-反魔幻定向,并且该结论对于列表形式也成立,其中列表中元素均为正实数.由于平面图是5-退化的,因此每一个平面图都存在一个局部7-反魔幻定向.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】