1-平面圖的無(wú)圈邊.pdf

1、圖 G的無(wú)圈fc-邊染色是指圖G的一個(gè)正常邊染色且不產(chǎn)生雙色圈的fc-邊染色.圖G的無(wú)圈邊染色數(shù)x U G)是使得圖G有一個(gè)無(wú)圈fc-邊染色的最小整數(shù)k.在1978年， Fiamcik提出了任意圖的無(wú)圈邊染色數(shù)不超過(guò)A(G)+2的猜想，A(G)表示圖G的最大度.在2001年，Alon等人又一次在文獻(xiàn)中陳述了這個(gè)猜想.研宄者們稱這個(gè)猜想為“無(wú)圈邊染色猜想”，簡(jiǎn)記為“AECC”.圖G是k-閉極小圖，是指最大度不超過(guò)k的圖G,其任意真子圖H都

2、滿足xUG)> k且x'JH)< k.圖G是1-平面圖，是指它可以畫在平面上使得每一條邊至多與一條其他的邊相交.圖G是平面圖，是指它可以畫在平面上使得每一條邊都不與其他的邊相交.很明顯平面圖符合1-平面圖的定義，即平面圖都是1-平面圖.
　　本論文共證明了兩個(gè)結(jié)論，一個(gè)是不含三角形的1-平面圖G,無(wú)圈邊染色數(shù)xl(G)< A(G)+14.另一個(gè)是滿足圍長(zhǎng)至少為5的1-平面圖G,無(wú)圈邊染色數(shù)xl(G)< A(G)+7.
　　第

3、一章是引言，介紹圖論的起源，圖論起源于非常經(jīng)典的哥尼斯堡七橋問(wèn)題.介紹圖論的歷史發(fā)展，圖的染色問(wèn)題的意義，圖的無(wú)圈邊染色相關(guān)概念的產(chǎn)生，并對(duì)論文的主要內(nèi)容進(jìn)行簡(jiǎn)要介紹.
　　第二章是基礎(chǔ)知識(shí)，闡述全文將要用到的一些基本概念和符號(hào)，以及一些關(guān)于圖的無(wú)圈邊染色數(shù)的研宄成果.按照研宄對(duì)象分為圍長(zhǎng)比較大的圖，正則圖，最大平均度比較小的圖，最大度比較小的圖，1-平面圖，平面圖，圍長(zhǎng)比較大的平面圖，不含短圈相互關(guān)聯(lián)的平面圖，不含短圈的平面圖，

4、外平面圖這些類進(jìn)行介紹.
　　第三章是一些結(jié)構(gòu)引理，主要是為后面兩章的證明做準(zhǔn)備.
　　第四章是要證明的第一個(gè)結(jié)果，在已有1-平面圖無(wú)圈邊染色數(shù)結(jié)論的基礎(chǔ)上，結(jié)合已知的結(jié)構(gòu)引理，改進(jìn)了W ang等人證明的結(jié)果，即不含三角形的1-平面圖的無(wú)圈邊染色數(shù)不超過(guò)A+17,本篇文章用權(quán)轉(zhuǎn)移方法證明了不含三角形的1-平面圖的無(wú)圈邊染色數(shù)不超過(guò)A+14.
　　第五章是要證明的第二個(gè)結(jié)果，通過(guò)添加圍長(zhǎng)條件并結(jié)合已知的結(jié)構(gòu)引理，證明了圍