邊染色圖中的長異色路.pdf

1、一個(gè)圖G=(V(G),E(G))的邊染色可以看成是從其邊集合E(G)到自然數(shù)集合上的一個(gè)映射C。如果圖G有這樣的一個(gè)染色C,我們就稱圖G為一個(gè)邊染色圖,記作(G,C),并用C(e)來表示邊e的顏色。圖G的一條異色路是指其中任意兩條邊上的顏色都不相同的路。給定圖G中的一個(gè)頂點(diǎn)v,如果有一條與之關(guān)聯(lián)的染i色的邊,則稱顏色i在這個(gè)頂點(diǎn)v上表現(xiàn)。頂點(diǎn)v的色度dc(v)是指在項(xiàng)點(diǎn)v上表現(xiàn)的不同顏色的個(gè)數(shù),而其色鄰域CN(v)是指在頂點(diǎn)v上表現(xiàn)的不

2、同顏色所組成的集合。給定一個(gè)正整數(shù)k,如果對圖G的任意一個(gè)頂點(diǎn),都有至少k種不同的顏色在其上表現(xiàn),即任意頂點(diǎn)v∈V(G)都滿足dc(v)≥k,則稱圖G的這個(gè)邊染色C是一個(gè)k-優(yōu)染色。 在上世紀(jì)中葉,出現(xiàn)了許多關(guān)于長路和長圈的重要定理。1952年,Dirac證明對于一個(gè)給定的圖G和一個(gè)給定的正整數(shù)d,如果圖G中的任意一個(gè)頂點(diǎn)u都滿足d(u)≥d,則圖G中有一條長度至少為d的長路。1960年,Ore指出對于任意一個(gè)n個(gè)頂點(diǎn)的圖G,如

3、果G中任意一對不相鄰的頂點(diǎn)u和v都滿足d(u)+d(v)≥n,則圖G含有一個(gè)Hamilton圈。1963年,Pósa證明對于一個(gè)2-連通圖G和一個(gè)正整數(shù)c,如果圖G中的任意一對不相鄰的頂點(diǎn)u和v都滿足d(u)+d(v)≥c,則圖G中有一個(gè)Hamilton圈或者一個(gè)長度至少為c的圈,這就意味著圖G中有一條Hamilton路或者一條長度不小于c-1的路。 此后,人們把這些定理推廣到了賦權(quán)圖中的重路和重圈上,得到了很多相關(guān)的結(jié)果。我們

4、很自然的會問：這些定理可以推廣到邊染色圖中的異色路上嗎?由于邊染色圖中的異色子圖研究起來比較困難,到目前為止關(guān)于異色路的結(jié)果還比較少,且絕大部分結(jié)果都是類Ramsey的,這就意味著這些結(jié)果大多只研究了邊染色完全圖中的異色路。2005年,Broersma和李學(xué)良教授等人研究了邊染色一般圖中的異色路問題。他們得到了如下兩個(gè)結(jié)果：給定一個(gè)邊染色圖G和一個(gè)正整數(shù)k,如果圖G的每個(gè)頂點(diǎn)v都滿足dc(v)≥k,則對于圖G中的任意一個(gè)頂點(diǎn)z,圖G中都

5、有一條長度不小于[k+1/2]的異色z-路；給定一個(gè)邊染色圖G和一個(gè)大于1的正整數(shù)s,如果圖G中任意兩個(gè)頂點(diǎn)u和v都滿足｜CN(u)∪CN(v)｜≥s,則圖G中有一條長度不小于[s/3]+1的異色路。在本文中我們改進(jìn)了他們的結(jié)果且給出了關(guān)于邊染色圖中的長異色路長度的一些更好的下界。本文分為兩部分,第一部分主要研究了一般邊染色圖中的長異色路問題,第二部分主要研究了不含異色三角形的邊染色圖中的長異色路問題。 第一部分由第二章和第三章

6、組成。第二章中我們研究了k-優(yōu)染色下圖G中的長異色路。我們證明：如果3≤k≤7,則圖G中有一條長至少為k-1的異色路；而如果k≥8,則圖G中有一條長至少為[2k/3]+1的長異色路。 第三章中我們研究了滿足色鄰域條件的邊染色圖G中的長異色路。所謂邊染色圖G滿足色鄰域條件是指對G中的任意一對頂點(diǎn)u和v,都有｜CN(u)∪CN(v)｜≥s成立,這里s是一個(gè)給定的正整數(shù)。我們證明了在這個(gè)條件下,圖G中有一條長至少為[s+1/2]的異色

7、路,并舉例說明了我們的這個(gè)下界是最優(yōu)的。 本文的第二部分是第四章,在其中我們考慮了不含異色三角形的邊染色圖中的長異色路問題。我們具體研究了兩種不同類型的不含異色三角形的圖,一種是Gallai染色下的完全圖,即不含異色三角形的完全圖；另一種是不含異色三角形的k-優(yōu)染色圖。在研究不含異色三角形的完全圖Kn時(shí),我們發(fā)現(xiàn)對于圖Kn中的任意一個(gè)頂點(diǎn)v,圖Kn中都有一條長度至少為dc(v)的異色v-路,我們還舉例說明這個(gè)界是最優(yōu)的。對于不含