论文部分内容阅读
染色问题是图论研究的经典领域,它源自于四色定理的研究,是图论研究中一个很活跃的课题.随着染色问题在现实中被广泛应用,各类染色问题被相继提出并加以发展、应用.
图G的一个(正常)к-染色是将к种染色分配给G的顶点集V(G),使得相邻两顶点的颜色不同.定义色数为:X(G)=min{к|图G有к-染色}.类似的,图G的一个(正常)к-边染色是将к种染色分配给G的边集E(G),使得有公共端点的两边的颜色不同.边色数X<>(G)=min{к|图G有尼к-边染色).
全染色的概念是对点染色和边染色的推广,是图论染色的一个传统问题,由Vizing(1964)<[24]>和Behzacl(1965)<[25,26]>各自独立提出的.图的全染色是对图的点,边进行染色.使得相邻或相关联的两元素染色不同.图的全色数XT(G)=min{к|图G有一个к-全染色}.在全染色的基础上,张忠辅提出了邻点可区别的全染色的概念并给出了相应的猜想和两个引理.
张忠辅定义的邻点可区别的全染色如下:设G(V,E)为阶不小于2的简单连通图,к为正整数,令映射f:V(G)UE(G)→{1,2,…,к).对任意u∈V(G),如果(1)对任意uu,uw∈E(G),u≠w,有f(uu)≠f(uw).(2)对任意眦,uu∈ E(G)有f(u)≠f(u)≠f(u)≠(uu)≠f(u).则称f为图G的一个к-全染色,简记为к-TC.若还满足(3)对任意uu∈E(G),c(u)≠C(u),其中C(u)={f(u))u(f(uu)|uu ∈E(G)).那么称厂为图G的一个к-邻点可区别全染色,简记为к-AVDTC.图G的全色数XT(G)(或记为X″(G))=min{k|图G有κ-全染色}.图G的邻点可区别的全色数X<,a>t(G)=min{k}图G有κ-AVDTC}.张忠辅给出了关于邻点可区别全染色的两个引理:对任意阶为n(n≥2)的简单连通图G,邻点可区别全色数X<,at>(G)存在,并且X<,at>(G)≥△(G)+1.若图G(V, E)有两个相邻的最大度点,则有X<,at>(G)≥a(a)+2.张忠辅在文献[4]中给出了邻点可区别全色数猜想:对任意阶为n(n≥2)的简单连通图G,有X<,at>(G)≤△(G)+3.
确定一任意给定图的邻点可区别全色数是NP-困难的.目前关于路,圈,完全图,完全二部图,星,扇,轮,树等特殊图的邻点可区别全色数已给出.另外上述特殊图的Mycielski图,联图和乘积图的邻点可区别全色数已有一些结果.同时,Petersen图,Heawood图,Thomassen图的邻点可区分全色数也已得到结果.
1880年,边染色的概念被提出,在边染色问题的研究巾有著名的四色定理.1964年,Vizing得出一个重要的定理即对任意的简单图G,有△(G)≤X＇(G)≤△(G)+1.
1974年,R.P.Gupta对边覆盖染色进行了研究.图G的边覆盖染色是对图G的所有边进行染色使得每种颜色在每个顶点上至少出现一次.满足图G有一个k-边覆盖染色的最人正整数k称为图G的边覆盖色数,记为X＇<,c>(G).同年,Cupta证明了对任意的简单图G,有δ(G)-1≤X＇<,c>(G)≤δ(G). 若X＇<,c>=δ(G),则称G是第一类的.若X＇<,c>(G)=δ(G)-1,则称G是第二类的.刘桂珍老师及苗连英,宋惠敏等对图的边覆盖染色进行了进一步的研究并2006年,孙磊老师受边覆盖染色的启发提出了全色极大团染色的概念.全色极大团染色是对图G的顶点进行染色,使得G的每个极大团所有颜色均出现.满足图G有一个k-全色极大团染色的最大正整数k称为图G的全色极大团色数,记为x<,maxcT>(G).显然有x<,maxcT>(G)≤min{|H‖H为G的极大团).
本文一部分主要探讨了轮,完全图的Hajos sum的邻点可区别全色数.另外还得到了特殊图P<,n>,花G的邻点可区别全色数.另一部分讨论了特定条件下全色极大团染色与边覆盖染色的等价性,给出了联图,复合图,笛卡尔乘积图,外平面图的全色极大团色数,并给出了K<,n>-M,C<,n>,Mycielski图,类Mycielski图的全色极大团色数.