關于圖的均勻染色理論的繼續(xù)研究.pdf

1、本文考慮的圖均為有限、簡單、無向圖，對于任意一個圖G，的頂點集合，階(頂點數(shù))，邊集合，邊數(shù)，最大度，最小度，圍長，直徑和面集，分別用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有一

2、個正常k-頂點染色，就稱G是k-頂點可染色的.圖G的點色數(shù)是指使G有正常k-頂點染色的數(shù)k的最小值，用x(G)表示.
　　 設φ是圖G的一個正常的頂點染色，若φ的任何兩種不同顏色所染的頂點數(shù)目至多相差1，稱φ是G的一個均勻染色.如果φ足圖G的一個均勻k-頂點染色，稱φ是G的一個均勻k-染色.圖G可進行均勻k-染色的最小整數(shù)七稱為G的均勻色數(shù).記為xe(G).
　　 現(xiàn)在已經(jīng)有了很多關于圖的均勻染色的結論，比較著名的是Ha

3、jnal和Szemerédi得到的這個結果：
　　 Hajnal-Szemerédi定理：給定一個正整數(shù)r，如果一個圖G最大度不超過r，那么這個圖G存在一個均勻(r+1)-染色.
　　 關于均勻染色理論，有以下兩個猜想.
　　 猜想1：設G是一個連通圖.如果G既不是完全圖，奇圈又不是完全二部圖K2m+1，2m+1，△(G)=△，那么G存在均勻△-染色.
　　 猜想2：設r≥3，如果對于圖G的任一條邊xy，

4、都有d(x)+d(y)≤2r，并且G不能均勻r-染色，那么G一定含有kr+1或者km，2r-m.(m為奇數(shù))
　　 本文所得到的第一個結論是證明了猜想2在一種特殊情況下是成立的.
　　 定理2.1當r>3時，在圖G中只有一對鄰點va，vb滿足d(va)+d(vb)=2r，其余各對鄰點的度數(shù)之和都小于2r，那么圖G可以均勻r-染色.
　　 在本文中，我們還定義了一種新的染色-樹染色.圖G的(t，k，d)-樹染色是指

5、把圖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)-樹色數(shù)，記為Xk，d(G).
　　 圖的均勻(t，k，d)-樹染色是指G存在一個(t，k，d)-樹染色，v1，v2，…，vt是各個顏色的頂點集合，并且對于任意的i和j(1

6、≤i≤j≤t)，都有｜｜vi｜-｜vj｜｜≤1.圖G存在均勻(t，k，d)-樹染色的最小的t我們稱之為G的均勻(k，d)-樹色數(shù)，記為Xk，d=(G).
　　 圖的全均勻(t，k，d)-樹染色是指對所有的t'≥t，G都存在一個均勻(t'，k，d)-樹染色，圖的全均勻(k，d)-樹色數(shù)記為Xk，d≡(G).若k=+∞，d=+∞，我們就把(t，k，d)-樹染色稱為t-樹染色，把均勻(t，k，d)-樹染色稱為均勻t-樹染色.最小的t-