论文部分内容阅读
图论是新兴的数学分支，应用十分广泛，图的染色理论是图论的重要组成部分，其中可区别染色问题是主要研究的课题之一.本文所研究的图的可区别染色主要包括以下几个方面:子母图的邻点可区别边色数的关系，图的D(2)-点可区别全染色，r-强点可区别全染色，D(β)-点可区别边染色以及邻点可区别V-全染色. 本文分五章进行讨论: 第一章主要给出了相关的概念和文中涉及到的符号. 第二章完全刻画了树图与单圈图的子母图的邻点可区别边色数的关系，并证明了对于树图以及最大度不小于5的单圈图，其子图的邻点可区别边色数是不超过母图的.最后还给出了一些子图色数超过母图的一些反例. 第三章根据Halls定理，给出一般图G的D(2)-点可区别全色数的一个上界为(△(G)+1)2+1.而且还证明了对于树图T，若存在两个距离不超过2的最大度点，则其D(2)-点可区别全色数为△(T)+2;否则，其D(2)-点可区别全色数为△(T)+1. 第四章通过分析图的结构，给出了K3-free图G的1-强点可区别全色数的一个上界是4△(G)2-△(G).对于树图T，证明了其2-强点可区别全色数不超过△(T)+3，而且它的3-强点可区别全色数是不超过3△(T)+1的. 第五章用概率方法中的Lovász局部引理，分别给出了图的D(β)-点可区别边色数及邻点可区别V-全色数的一个较小的上界.