圖的全染色、（鄰）點(diǎn)可區(qū)別全染色及分?jǐn)?shù)染色.pdf

1、染色問題及許多圖理論都是源自四色問題的研究.另外染色問題在組合分析和實(shí)際生活中有著廣泛的應(yīng)用，是圖論研究中一個很活躍的課題，各類染色問題被相繼提出并加以發(fā)展、應(yīng)用. 全染色的概念是對點(diǎn)染色和邊染色的推廣，圖的所有元素(頂點(diǎn)和邊)都將染色且任相鄰或關(guān)聯(lián)的元素染色不同.全染色是圖論染色的一個傳統(tǒng)問題，由Vizing(1964)[23]和Behzad(1965)[24,25]各自獨(dú)立提出的，同時分別給出全染色猜想.點(diǎn)可區(qū)別全染色和鄰點(diǎn)

2、可區(qū)別全染色[2'是染色問題的新生點(diǎn)，近來由張忠輔提出并給出了相應(yīng)的兩個猜想. 本文一部分主要探討了Mycielski構(gòu)造圖和Cartesian乘積圖在全染色、點(diǎn)可區(qū)別全染色及鄰點(diǎn)可區(qū)別全染色方面與原基礎(chǔ)圖的關(guān)系，從而也得到了它們滿足全染色猜想和鄰點(diǎn)可區(qū)別全染色猜想的一些充分條件；另外還得到特殊圖類(如：Pk+1n,n,Gk+1n,n,Ck+1n,n(k=0，1，…，n-1，n≥3)，Gn，n;W2n)在此染色方面的一些結(jié)果.另

3、一部分首先考慮了Kneser圖和Ga，b圖的m-層色數(shù),Kneser圖只解決了部分m-層色數(shù)，Ga,b圖的m-層色數(shù)本文中已完全確定；其次討論了Cartesian乘積圖的分?jǐn)?shù)染色，目前只解決了部分圖乘積的分?jǐn)?shù)色數(shù)；最后通過分?jǐn)?shù)全染色和分?jǐn)?shù)全團(tuán)的對偶關(guān)系和分?jǐn)?shù)全染色的概念探討了幾類特殊圖(如：圈，完全圖，完全二部圖，平衡完全r-部圖)的分?jǐn)?shù)全色數(shù). 在本文中，我們主要得到結(jié)論如下：我們稱由Mycielski作圖法[21]得到圖為M

4、ycielski圖.給定圖G，頂點(diǎn)集V={v1，v2，…，vn}，圖G的Mycielski圖(記為M(G))定義為：頂點(diǎn)集V(M(G))=V∪{v'1，v'2，…，v'n，ω}，邊集E(M(G))=E(G)∪{viv'j|vivj∈E(G)，i，j=1，…，n}∪{v'iω|i=1，…，n}.定理2.1.1設(shè)G為n階圖.χT(G)≥n時，χT(M(G))≤χT(G)+△(G)；χT(G)＜n時,χT(M(G))≤n+△(G).推論2.1

5、.2設(shè)G為n階圖.若△(G)=n-1且χT(G)=△(G)+1，則χT(M(G))=△(M(G))+1.定理2.1.3設(shè)G為n階圖.χvt(G)≥n時，χvt(M(G))≤xvt(G)+△(G)；χvt(G)＜n時，χvt(M(G))≤n+△(G).定理2.1.4設(shè)G為δ(G)≥2的n階圖，尼為正整數(shù).若χvt(G)≤△(G)+k且△(G)+k≥n，則χvt(M(G))≤△(M(G))+k.推論2.1.5設(shè)G為n階圖，k為正整數(shù).若χa

6、t(G)≤△(G)+k且△(G)+k≥n，則χat(M(G))≤△(M(G))+k.推論2.1.6設(shè)圖G滿足推論2.1.4的條件，若鄰點(diǎn)可區(qū)別全染色猜想對G成立，則M(G)也滿足此猜想.進(jìn)一步，若k=1，則上面兩結(jié)論變成χvt(M(G))=△(M(G))+1和χat(M(G))=△(M(G))+1. 以下四個結(jié)論是關(guān)于Cartesian乘積圖鄰點(diǎn)可區(qū)別全染色的，對圖G1=(V1，E1)和G2=(V2，E2)，它們的Cartesi

7、an乘積圖G1×G2的頂點(diǎn)集為V1×V2，兩頂點(diǎn)(v1，u1)和(v2，u2)相鄰當(dāng)且僅當(dāng)或者v1v2∈E1且u1=u2∈V2或者v1=v2∈V1且u1u2∈E2. 定理2.2.2設(shè)G，H為兩個圖，k為正整數(shù)(k＞1).若△(G)+2≤χat(G)≤△(G)+k，χ’(H)=△(H)且χ(H)≤△(G)+k，則χat(G×H)≤△(G×H)+k. 定理2.2.3若圖G滿足鄰點(diǎn)可區(qū)別全染色猜想，χ’(H)=△(H)且χ(H

8、)≤χat(G)，則G×H也滿足此猜想. 定理2.2.4設(shè)G，H為兩個圖，k為正整數(shù)(k＞1).若△(G)+2≤χat(G)≤△(G)+k且χ(H)≤△(G)+k，則χat(G×H)≤△(G×H)+k+1. 推論2.2.5設(shè)G，H為兩個圖，k為正整數(shù)(k＞1).若χat(G)≤△(G)+2且χ(H)≤χat(G)，則G×H滿足鄰點(diǎn)可區(qū)別全染色猜想. 設(shè)Pn=u1u2…un和Pn=v1v2…vn為兩條路.在兩路間逐

9、次疊加匹配uivi，uivi+1，…，uivi+k，…,uivi+(n-1)(i=1，2，…，n，k=0，1，…，n-1，當(dāng)i+k＞n+1時，i+k為modn意義下的加法)，這樣可得到一系列圖：P(1)n,n,P(2)n,n,…，P(k+1)n,n,…，P(n)n,n=Pn∨Pn. 設(shè)V1={u1，u2，…，un}，V2={v1，v2，…，vn}為兩頂點(diǎn)集，u1u2…unu1和v1v2…vnv1為兩個圈.類似的，在兩部(V1，V

10、2)間逐次疊加上述匹配，可以得到一系列正則二部圖，記為：G(1)n,n，G(2)n,n，…，G(k+1)n,n,…，G(n)n,n=Kn,n.在兩圈間逐次疊加同樣的匹配，可得到一系列正則圖：C(1)n,n，C(2)n,n,…，C(k+1)n,n,…，C(n)n,n=Cn∨Cn，且△(C(k+1)n,n)=k+3. 定理2.3.1χat(P(k+1)n,n)=△(P(k+1)n,n,)+2=k+5(k=0，1，…，n-1，n≥3)

11、. 定理2.3.2χat(G(k+1)n,n)=△(G(k+1)n,n)+2=k+3(k=0，1，…，n-1，n≥3). 推論2.3.3χT(P(k+1)n,n)≤△(P(k+1)n,n)+2，χT(G(k+1)n,n)≤△(G(k+1)n,n)+2，即P(k+1)n,n,G(k+1)n,n滿足全染色猜想. 定理2.3.4χT(C(k+1)n,n)≤△(C(k+1)n,n)+2=k+5(k=0，1，…，n-1，n

12、≥3). 定理2.3.6χat(W2n)={6n=3,4{n+1n≥5推論2.3.7W2n滿足全染色猜想，而且當(dāng)n≥5時χT(W2n)=△(W2n)+定理2.3.8若G為邊連通度λ(G)=1的圖，設(shè)u0v0為其任意割邊，χat(G)={△(G)+2若d(u0)=d(v0)=△(G)且χat(G1∪u0v0){=χat(G2∪u0v0)=△(G)+1{max{χat(G1∪u0v0),χat(G2∪u0v0)}否則若兩頂點(diǎn)為不交集

13、合，則兩頂點(diǎn)相鄰.Ga，b圖為一類循環(huán)圖[29]，頂點(diǎn)集為{0，1，…，a-1}，頂點(diǎn)i，j相鄰當(dāng)且僅當(dāng)b≤|i-j|≤a-b.Kneser圖和Ga，b圖分別在分?jǐn)?shù)染色和圓染色中起著重要的作用，它們在其中所扮演的Stahl[17]提出猜想：對任意正整數(shù)m，χm(Ka：b)=a-2b+2m均成立.[14]已證明當(dāng)1≤m≤b時猜想是成立的，下面的定理將說明m＞b時定理3.1.2χmb(Ka：b)=ma(a，b，m為正整數(shù)). 定理3

14、.1.4設(shè)a，b，m為正整數(shù),χm(Ga,b)=χ(Gma,b)=[ma/b]. 定理3.2.3若G含Hamilton圈，H為二部圖，則χf(G×H)=χf(G). 定理3.2.4設(shè)a,b為正整數(shù)且a≥2b，若χ(H)≤「a/b」，則χf(Ga,b×H)=χf(Ga，b)=a/b. 引理3.3.1設(shè)G為一個圖，若χ"(G)=△(G)+1則χ"f(G)=χ"(G)=Δ(G)+1定理3.3.2設(shè)Gn為n階的圈，k為正

15、整數(shù)，則χ"f(Cn)={3n=3k{3+1/kn=3k+1{3+1/2k+1n=3k+2定理3.3.3[12]對完全圖Kn;χ"f(Kn)=χ"(Kn)={nn是奇數(shù){n+1n是偶數(shù)定理3.3.4[12]對完全二部圖Km，n,χ"f(Km,n)=χ"(Km,n)={max{m,n}+1m≠n{n+2m=n定理3.3.5[13]χ"f(K(r，n))=χ"(K(r，n))={Δ(K(r,n))+2若r=2或r為偶數(shù)且n為奇數(shù){Δ(K(r