圖的均勻(t,k,d)-樹染色.pdf

1、對任意圖G，它的頂點(diǎn)集、邊集、最大度、最小度分別用V(G)、E(G)、△(G)、δ(G)表示。
　　 圖G=(V,E)中，設(shè)V＇是V的一個非空子集。若圖G有一個子圖，其頂點(diǎn)集為V＇，邊集合為兩端點(diǎn)均在V＇中的邊所構(gòu)成的集合，那么這一子圖稱為V＇在G中的導(dǎo)出子圖，記為G[V＇]。
　　 對于V的一個子集S，若S中任意兩點(diǎn)在圖G中不相鄰，那么我們就稱S為獨(dú)立集；若S中任意兩點(diǎn)在圖G中相鄰，那么我們就稱S為團(tuán)。
　　

2、圖G的一個點(diǎn)邊交替出現(xiàn)且點(diǎn)、邊不重合的有限序列稱為路。一條路所含的邊數(shù)稱為路的長度。圖G=(V，E)中兩點(diǎn)u，v之間的所有路的路長最小值稱為u，v之間的距離。圖G中任意兩點(diǎn)之間距離的最大值稱為圖的直徑。
　　 起點(diǎn)、終點(diǎn)重合，且內(nèi)部點(diǎn)不重合的路稱為圈。
　　 若圖G的兩個點(diǎn)u，v之間有一條(u，v)-路，那么稱u，v是聯(lián)通的。因此，存在V的一個劃分V1，V2，…，Vt，其中u，v聯(lián)通當(dāng)且僅當(dāng)u，v同屬于Vi。導(dǎo)出子圖G[

3、V1]，G[V2]，…，G[Vt]稱為G的分支。若G只有一個分支，則G是聯(lián)通的。
　　 若圖G是一個無圈的連通圖，那么我們稱其為樹。若圖G的各連通分支都是樹，則稱其為森林。
　　 若圖G中任意不同的兩點(diǎn)之間都有一條邊存在，那么稱圖G為完全圖。有n個點(diǎn)的完全圖記為Kn。
　　 若圖G=(V，E)中，點(diǎn)集V可以分成兩個子集X和Y，使得圖G中任意一條邊有一個端點(diǎn)在X中，一個端點(diǎn)在Y中，則稱圖G為二部圖。若X中每個點(diǎn)都與

4、Y中每個點(diǎn)相鄰，那么這樣的二部圖稱為完全二部圖。如果|X|=m，|Y|=n，那么這樣的圖可以記為Km，n。
　　 若圖G=(V,E)中，點(diǎn)集V可以分成n個子集X1，X2，…，Xn，使得圖G中任意一條邊有一個端點(diǎn)在Xi中，一個端點(diǎn)在Xj中，則稱圖G為n部圖。若Xi中每個點(diǎn)都與Xj中每個點(diǎn)相鄰，那么這樣的n部圖稱為完全n部圖。如果|Xi|=li，那么這樣的圖可以記為Kl，，l2，…，ln。
　　 給定圖G=(V,E)，若V=

5、S+K，且S為獨(dú)立集，K為團(tuán)，則稱G為分裂圖。
　　 本文主要研究圖的均勻(t，k，d)-樹染色。
　　 圖G的均勻(t，k，d)-樹染色是指把圖G的點(diǎn)集分解為V1，V2，…，Vt，使得對于每個Vi，它的導(dǎo)出子圖G[Vi]的任何一個分支都是直徑至多為k、最大度至多為d的樹（k≥0，d≥0），且對任意i，j（1≤i＜j≤t），有||Vi|-|Vj||≤1。
　　 均勻(t，k，d)-樹色數(shù)是指圖G的所有均勻(t，k

6、，d)-樹染色中最小的t，記為X=k,d，。圖的全均勻(t，k，d)-樹色教是指對所有的t≥t，G都存在一個均勻(t＇，k，d)-樹染色，且取值最小的t，記為X≡k,d。
　　 本文首先將討論一些特殊圖的均勻樹染色問題，即完全圖、分裂圖、完全二部圖K1，n以及完全n部圖Kl1，l2，…，ln（li=1，1≤i≤k)。
　　 接著給出三個定義：
　　 (1)如果x mod n=y，我們稱Mn(x)=y，其中n為整數(shù)

7、。
　　 (2)Z(x)=max｛3,max｛k|Mi(x)=0,i≤k｝｝。
　　 (3)W(x)=max｛j「x/i」≥「x/i+1」,i≤k｝｝。
　　 當(dāng)k=1時(shí)，對于完全二部圖，我們證明:
　　 定理0.0.1(1)若M3(m)+M3(n)≥3，則X≡1,1(Km,n)=「m/3」+「n/3;
　　 (2)若M3(m)+M3(n)≤2，且r=min｛max｛Z(m),Z(n)｝，W(m)