1-平面圖的無圈邊.pdf

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

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

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

4、外平面圖這些類進行介紹.
　　第三章是一些結構引理，主要是為后面兩章的證明做準備.
　　第四章是要證明的第一個結果，在已有1-平面圖無圈邊染色數結論的基礎上，結合已知的結構引理，改進了W ang等人證明的結果，即不含三角形的1-平面圖的無圈邊染色數不超過A+17,本篇文章用權轉移方法證明了不含三角形的1-平面圖的無圈邊染色數不超過A+14.
　　第五章是要證明的第二個結果，通過添加圍長條件并結合已知的結構引理，證明了圍