若干圖的無(wú)圈邊染色.pdf

1、對(duì)于一個(gè)給定的圖G，分別用V(G)，E(G)和△(G)表示它的頂點(diǎn)集，邊集和最大度.圖G的正常k-邊染色是指一個(gè)映射c:E(G)→{1，2，...,k}使得相鄰的邊染不同的顏色.圖G的一個(gè)正常的k-邊染色稱(chēng)為無(wú)圈的，如果圖G中不含雙色圈，換句話(huà)說(shuō)，圖G中任何兩種顏色的邊導(dǎo)出的子圖是一個(gè)森林.圖G的無(wú)圈邊色數(shù)，用a'(G)表示，是使圖G存在無(wú)圈邊染色所需的最少顏色數(shù).
　　 1973年，Grünbaum提出了無(wú)圈點(diǎn)染色的概念，而無(wú)

2、圈邊染色的定義最早是由Fiam(c)ík給出的.1991年，Alon等人證明了:對(duì)任意圖G，都有a'(G)≤64△(G).1998年，Molly和Reed把上界改進(jìn)到a'(G)≤16△(G).Fiam(c)ík(1978)和Alon，Sudakov, Zaks(2001)先后提出了著名的無(wú)圈邊染色猜想:
　　 對(duì)任意簡(jiǎn)單圖G，都有a'(G)≤△(G)+2.
　　 這個(gè)猜想至今仍未得到證實(shí)，只知一些特殊圖類(lèi)滿(mǎn)足該猜想.本學(xué)

3、位論文在前人工作的基礎(chǔ)上，圍繞若干圖的無(wú)圈邊染色問(wèn)題展開(kāi)研究，共分四章.
　　 在第一章，我們介紹圖論中的基本概念，簡(jiǎn)單綜述圖的無(wú)圈邊染色研究過(guò)程中的一些基本結(jié)果并呈現(xiàn)了本文的主要研究結(jié)果.
　　 在第二章，我們研究了2-外平面圖的無(wú)圈邊染色，證明了:對(duì)2-外平面圖G，有a'(G)≤△(G)+2，即無(wú)圈邊染色猜想對(duì)2-外平面圖族成立.
　　 在第三章，我們研究了不含特殊短圈平面圖的無(wú)圈邊染色，證明了:若平面圖G不