完全二部圖的單色樹劃分和單色樹覆蓋.pdf

1、一個(gè)圖G=(V(G)，E(G))的邊染色是指從其邊集合E(G)到自然數(shù)子集{1，2，…，r}上的一個(gè)滿射C。如果圖G有這樣的一個(gè)染色C，我們就稱圖G是一個(gè)邊染色圖，或r-邊染色圖，并用C(e)來表示邊e的顏色。給定圖G中的一個(gè)頂點(diǎn)ν，頂點(diǎn)ν的色鄰域CN(ν)是指集合{C(e)：e與ν關(guān)聯(lián)}。頂點(diǎn)ν的色度記為dc(ν)=｜CN(ν)｜。一棵樹被稱為單色的是指這棵樹中的所有邊上所染顏色都相同。
　　 1991年，Erdos，Gyar

2、fas和Pyber提出了邊染色圖的單色樹劃分?jǐn)?shù)的概念。r-邊染色圖G的單色樹劃分?jǐn)?shù)，或簡(jiǎn)稱為樹劃分?jǐn)?shù)，記作tr(G)，是指最小的k滿足：對(duì)于G的任意r-邊染色，圖G的頂點(diǎn)集合可被至多k個(gè)頂點(diǎn)不交的單色樹覆蓋。Erdos，Gyarfas和Pyber猜想r-邊染色完全圖的單色樹劃分?jǐn)?shù)是r-1，其中r≥2，并且他們證明了r=3時(shí)猜想的正確性。猜想對(duì)于r=2的情況等價(jià)于Erdos和Rado的斷言：對(duì)任意的圖G，圖G和圖G的補(bǔ)圖至少有一個(gè)連通。對(duì)

3、于無限完全圖，Hajnal等人證明了一個(gè)r-邊染色無限完全圖的單色樹劃分?jǐn)?shù)至多是r。對(duì)于有限完全圖，Haxell和Kohayakawa證明了當(dāng)n≥3r4r!(1-1/r)3(1-r)logr，任意r-邊染色完全圖Kn含有至多r個(gè)兩兩不同色的單色樹，并且他們的頂點(diǎn)集合劃分了Kn的頂點(diǎn)集合。Haxell和Kohayakawa還證明了當(dāng)n充分大時(shí)，r-邊染色的完全二部圖Kn，n的單色樹劃分?jǐn)?shù)至多是2r。一般地，確定tr(G)的精確的值是很困難

4、的。
　　 與單色樹劃分?jǐn)?shù)相關(guān)的一個(gè)問題是r-邊染色圖G的單色樹覆蓋數(shù)，或簡(jiǎn)稱為樹覆蓋數(shù)，它是指最小的k滿足：對(duì)于G的任意r-邊染色，圖G的頂點(diǎn)集合可被至多k個(gè)單色樹(可以相交)覆蓋。對(duì)于完全圖，以某個(gè)點(diǎn)為中心的所有單色星構(gòu)成了一個(gè)覆蓋，所以r-邊染色完全圖的單色樹覆蓋數(shù)至多是r。Erdos，Gyarfas和pyber關(guān)于樹劃分?jǐn)?shù)的猜想的一個(gè)弱形式是：r-邊染色完全圖的單色樹覆蓋數(shù)是r-1。
　　 本文分為三部分，第一部

5、分主要研究了2-邊染色完全二部圖的單色樹劃分問題，第二部分主要研究了3-邊染色完全等部二部圖的單色樹劃分問題，第三部分主要研究了2-邊染色和3-邊染色完全二部圖的單色樹覆蓋問題。
　　 第二章中我們研究了2-邊染色完全二部圖的單色樹劃分。對(duì)于2-邊染色的完全多部圖K(n1，n2，…，nk)，Kaneko，Kano和Suzuki證明了：設(shè)n1，n2，…，nk(2≤k)是滿足1≤n1≤n2≤…≤nk的整數(shù)，并且n=n1+n2+…+n

6、k-1，m=nk，則t2(K(n1，n2，…，nk))=[m-2/2n]+2。特別地，t2(Km，n)=[m-2/2n]+2，其中1≤n≤m。金澤民等人在2006年給出了2-邊染色的完全多部圖的單色樹劃分的多項(xiàng)式時(shí)間算法。第二章中我們給出了2-邊染色的完全二部圖的單色樹劃分更精細(xì)的刻畫，我們將2-邊染色完全二部圖分為幾種結(jié)構(gòu)，并給出每種結(jié)構(gòu)的單色樹劃分?jǐn)?shù)。我們得到如下結(jié)果。
　　 1.如果K(A，B)是一個(gè)2-邊染色完全二部圖，

7、則它是下面四種結(jié)構(gòu)中的一種：(1)K(A，B)有單色支撐樹，(2)K(A，B})∈M，(3)K(A，B)∈S2，(4)K(A，B)∈S1。
　　 2.如果K(A，B)∈M，則K(A，B)的頂點(diǎn)集可被兩個(gè)同色的單色樹覆蓋；如果K(A，B)∈S2，則K(A，B)的頂點(diǎn)集要么被一個(gè)孤立點(diǎn)和一個(gè)單色樹覆蓋，要么被兩個(gè)不同色的頂點(diǎn)不交的單色樹覆蓋；如果K(A，B)∈S1，并且m=｜A｜>｜B｜=n，則K(A，B)的頂點(diǎn)集可被至多[m-2/

8、2n]+2個(gè)頂點(diǎn)不交的單色樹覆蓋，并且存在邊染色使K(A，B)的頂點(diǎn)集恰被[m-2/2n]+2個(gè)頂點(diǎn)不交的單色樹覆蓋。
　　 第三章中我們研究了3-邊染色等部完全二部圖的單色樹劃分。我們給出了幾種色度條件下的單色樹劃分?jǐn)?shù)。設(shè)K(A，B)是一個(gè)3-邊染色等部完全二部圖，我們得到如下結(jié)果。
　　 1.如果存在色度為1的頂點(diǎn)，則t3(K(A，B))=3。
　　 2.如果每個(gè)頂點(diǎn)的色度都是2，則t3(K(A，B))=2。