本文關(guān)鍵詞：1-平面圖的無圈邊染色數(shù)

  更多相關(guān)文章： 無圈邊染色 無圈邊染色數(shù) 1-平面圖

【摘要】：圖G的無圈k-邊染色是指圖G的一個(gè)正常邊染色且不產(chǎn)生雙色圈的k-邊染色.圖G的無圈邊染色數(shù)χa'(G)是使得圖G有一個(gè)無圈k-邊染色的最小整數(shù)k.在1978年,Fiamcik提出了任意圖的無圈邊染色數(shù)不超過△(G)+ 2的猜想,△(G)表示圖G的最大度.在2001年,Alon等人又一次在文獻(xiàn)中陳述了這個(gè)猜想.研究者們稱這個(gè)猜想為"無圈邊染色猜想",簡記為"AECC".圖G是k-閉極小圖,是指最大度不超過k的圖G,其任意真子圖H都滿足χa'(G)且χa'(H)≤k.圖G是1-平面圖,是指它可以畫在平面上使得每一條邊至多與一條其他的邊相交.圖G是平面圖,是指它可以畫在平面上使得每一條邊都不與其他的邊相交.很明顯平面圖符合1-平面圖的定義,即平面圖都是1-平面圖.本論文共證明了兩個(gè)結(jié)論,一個(gè)是不含三角形的1-平面圖G,無圈邊染色數(shù)χa'(G)≤A(G)+ 14.另一個(gè)是滿足圍長至少為5的1-平面圖G,無圈邊染色數(shù)χa'(G)≤△(G)+7.論文內(nèi)容共分為五章.第一章是引言,介紹圖論的起源,圖論起源于非常經(jīng)典的哥尼斯堡七橋問題.介紹圖論的歷史發(fā)展,圖的染色問題的意義,圖的無圈邊染色相關(guān)概念的產(chǎn)生,并對論文的主要內(nèi)容進(jìn)行簡要介紹.第二章是基礎(chǔ)知識,闡述全文將要用到的一些基本概念和符號,以及一些關(guān)于圖的無圈邊染色數(shù)的研究成果.按照研究對象分為圍長比較大的圖,正則圖,最大平均度比較小的圖,最大度比較小的圖,1-平面圖,平面圖,圍長比較大的平面圖,不含短圈相互關(guān)聯(lián)的平面圖,不含短圈的平面圖,外平面圖這些類進(jìn)行介紹.第三章是一些結(jié)構(gòu)引理,主要是為后面兩章的證明做準(zhǔn)備.第四章是要證明的第一個(gè)結(jié)果,在已有1-平面圖無圈邊染色數(shù)結(jié)論的基礎(chǔ)上,結(jié)合已知的結(jié)構(gòu)引理,改進(jìn)了Wang等人證明的結(jié)果,即不含三角形的1-平面圖的無圈邊染色數(shù)不超過△+ 17,本篇文章用權(quán)轉(zhuǎn)移方法證明了不含三角形的1-平面圖的無圈邊染色數(shù)不超過△ + 14.第五章是要證明的第二個(gè)結(jié)果,通過添加圍長條件并結(jié)合已知的結(jié)構(gòu)引理,證明了圍長至少為5的1-平面圖的無圈邊染色數(shù)上界為△ + 7.
【學(xué)位授予單位】：河南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前4條

1 Wen Yao SONG;Lian Ying MIAO;;Acyclic Edge Coloring of Triangle-free 1-planar Graphs[J];Acta Mathematica Sinica;2015年10期

2 WAN Min;XU BaoGang;;Acyclic edge coloring of planar graphs without adjacent cycles[J];Science China(Mathematics);2014年02期

3 王維凡;舒巧君;;沒有K_4-圖子式的圖的無圈邊色數(shù)[J];中國科學(xué):數(shù)學(xué);2011年08期

4 ;Acyclic edge colorings of planar graphs and series-parallel graphs[J];Science in China(Series A:Mathematics);2009年03期

，

本文編號：1218689