论文部分内容阅读
本文考虑的图均为有限、简单、无向图,对于任意一个图G,的顶点集合,阶(顶点数),边集合,边数,最大度,最小度,围长,直径和面集,分别用V(G),∣G∣,E(G),∣E∣,△(G),δ(G),g(G),d(G)和F(G)来表示.在不引起混淆的情况下,我们把△(G),δ(G),g(G),d(G)简记为△,δ,g和d.
图G的一个正常k-顶点染色是指k种颜色在V(G)上的一种分配,使得任意两个相邻的顶点分配以不同颜色.若图G有一个正常k-顶点染色,就称G是k-顶点可染色的.图G的点色数是指使G有正常k-顶点染色的数k的最小值,用x(G)表示.
设φ是图G的一个正常的顶点染色,若φ的任何两种不同颜色所染的顶点数目至多相差1,称φ是G的一个均匀染色.如果φ足图G的一个均匀k-顶点染色,称φ是G的一个均匀k-染色.图G可进行均匀k-染色的最小整数七称为G的均匀色数.记为xe(G).
现在已经有了很多关于图的均匀染色的结论,比较著名的是Hajnal和Szemerédi得到的这个结果:
Hajnal-Szemerédi定理:给定一个正整数r,如果一个图G最大度不超过r,那么这个图G存在一个均匀(r+1)-染色.
关于均匀染色理论,有以下两个猜想.
猜想1:设G是一个连通图.如果G既不是完全图,奇圈又不是完全二部图K2m+1,2m+1,△(G)=△,那么G存在均匀△-染色.
猜想2:设r≥3,如果对于图G的任一条边xy,都有d(x)+d(y)≤2r,并且G不能均匀r-染色,那么G一定含有kr+1或者km,2r-m.(m为奇数)
本文所得到的第一个结论是证明了猜想2在一种特殊情况下是成立的.
定理2.1当r>3时,在图G中只有一对邻点va,vb满足d(va)+d(vb)=2r,其余各对邻点的度数之和都小于2r,那么图G可以均匀r-染色.
在本文中,我们还定义了一种新的染色-树染色.图G的(t,k,d)-树染色是指把图G的点集分解为V1,V2,…,Vt,即用t中颜色对图G的顶点进行染色,使得对每个Vi,(1≤j≤t),它的导出子图G[Vi]的任何一个分支都是直径至多为K,最大度至多为d的树,(k≥0,d≥0).图G存在(t,k,d)-树染色的最小的t称之为G的(k,d)-树色数,记为Xk,d(G).
图的均匀(t,k,d)-树染色是指G存在一个(t,k,d)-树染色,v1,v2,…,vt是各个颜色的顶点集合,并且对于任意的i和j(1≤i≤j≤t),都有||vi|-|vj||≤1.图G存在均匀(t,k,d)-树染色的最小的t我们称之为G的均匀(k,d)-树色数,记为Xk,d=(G).
图的全均匀(t,k,d)-树染色是指对所有的t≥t,G都存在一个均匀(t,k,d)-树染色,图的全均匀(k,d)-树色数记为Xk,d≡(G).若k=+∞,d=+∞,我们就把(t,k,d)-树染色称为t-树染色,把均匀(t,k,d)-树染色称为均匀t-树染色.最小的t-树染色称为点荫度,均匀t-树染色中最小的t称之为均匀点荫度,记为va=(G),全均匀点荫度记为va≡(G).
针对均匀树染色,主要得到了下面的两个结论:
定理3.1设G为-平面图且围长≥5.则全均匀点荫度va≡(G)≤3.
定理3.2设G为一平面图且围长≥6.若G为森林,则全均匀点荫度va≡(G)=1;否则全均匀点荫度va≡(G)=2.