论文部分内容阅读
图的染色与标号问题是图论中的重要分支,其研究历史久远,作为图论发展的先导之一:四色定理,就是典型的染色问题.一直以来,图的染色与标号问题备受关注,它们不仅在图论上扮演重要角色,而且在社会科学、生命科学等方面都有着广泛应用. 图的染色与标号本质上都是从图的点集或边集到实数集的映射.我们首先研究的是平面图的邻点可区别全染色问题. 图G的k-全染色是指用集合[k]中的颜色(即元素)对图的点和边同时进行染色,使得相邻的点、相邻的边以及相关联的点和边都染不同颜色.对于G的一个k-全染色ψ,我们用Cψ(v)来表示由点v以及v的所有关联边的颜色构成的集合.我们称点v和点u是冲突的,如果两点相邻且Cψ(v)=Cψ(u).如果G中任意两个邻点都不冲突,则称k-全染色ψ是邻点可区别的.我们将能够使得G具有邻点可区别全染色的最小的颜色数k称为图G的邻点可区别全色数,记作)xa"(G).2005年,Zhang等人首次提出这种染色并猜想:对于至少有两个点的连通图G,均有)xa"(G)≤△(G)+3.Cheng等人已经证明对于最大度至少为10的平面图,上述猜想成立,本文在第二章中证明了对于最大度△(G)≥9的平面图G,有)xa"(G)≤△(G)+3,改进了已有的结果,从而推动猜想的解决.进一步,对于最大度△(G)≥10的平面图G,我们得到了更好的上界,即xa"(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-反魔幻定向.