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

1、本文考慮的圖均為有限、簡(jiǎn)單、無(wú)向圖，對(duì)于任意一個(gè)圖G，的頂點(diǎn)集合，階(頂點(diǎn)數(shù))，邊集合，邊數(shù)，最大度，最小度，圍長(zhǎng)，直徑和面集，分別用V(G)，∣G∣，E(G)，∣E∣，△(G)，δ(G)，g(G)，d(G)和F(G)來(lái)表示.在不引起混淆的情況下，我們把△(G)，δ(G)，g(G)，d(G)簡(jiǎn)記為△，δ，g和d.
　　 圖G的一個(gè)正常k-頂點(diǎn)染色是指k種顏色在V(G)上的一種分配，使得任意兩個(gè)相鄰的頂點(diǎn)分配以不同顏色.若圖G有一

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

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

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

5、把圖G的點(diǎn)集分解為V1，V2，…，Vt，即用t中顏色對(duì)圖G的頂點(diǎn)進(jìn)行染色，使得對(duì)每個(gè)Vi，(1≤j≤t)，它的導(dǎo)出子圖G[Vi]的任何一個(gè)分支都是直徑至多為K，最大度至多為d的樹(shù)，(k≥0，d≥0).圖G存在(t，k，d)-樹(shù)染色的最小的t稱(chēng)之為G的(k，d)-樹(shù)色數(shù)，記為Xk，d(G).
　　 圖的均勻(t，k，d)-樹(shù)染色是指G存在一個(gè)(t，k，d)-樹(shù)染色，v1，v2，…，vt是各個(gè)顏色的頂點(diǎn)集合，并且對(duì)于任意的i和j(1

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