本文介紹最大度為4的圖的列表強邊染色問題的相關(guān)結(jié)果。設G是一個圖,E（G）與V（G）分別表示它的邊集與頂點集。設v∈V（G）,則點v在G中的度數(shù)表示為dG（V）,圖G的最大度和最小度分別表示為△（G）和δ（G）。圖的邊染色就是對圖中所有的邊都染上一個顏色并且要求任意兩條相鄰的邊所染的顏色都不同。圖的強邊染色則是在邊染色的基礎上進一步要求任意一條長度為3的路上的三條邊所染的顏色也都不同,并且記能夠?qū)DG進行強邊染色的最小顏色數(shù)為圖的強邊染色數(shù)χs’（G）。Erdos和Nesetril在1985年就強邊染色問題提出了一個重要猜想:如果圖G的最大度為△（G）,那么猜想中△ ≤ 3的情況已經(jīng)被證明。當△ = 4時,猜想的上界是20,但是目前并沒有得到證實,之前最好的結(jié)果是在2006年由Cranston證明的,Cranston證明了一個最大度為4的圖的強邊色數(shù)的上界是22,這一結(jié)果最近被Huang,Santana和Yu改進為21。關(guān)于△>4的情況,目前還沒有非常好的研究結(jié)果。列表強邊染色是廣義范圍的強邊染色,它要求在對圖G進行強邊染色時,必須預先給G的每條邊e都限制一個顏色列表L（e）,而... 

【文章來源】：山東大學山東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：41 頁

【學位級別】：碩士

【文章目錄】：
中文摘要
英文摘要
符號說明
第一章 前言
    1.1 基本概念
    1.2 強邊和列表強邊染色問題的背景和發(fā)展
    1.3 本文的主要結(jié)果及可討論的相關(guān)問題
第二章 預備知識及引用定理
    2.1 距離和距離類概念的引入
    2.2 引用的主要定理和引理
第三章 主定理極小反例的結(jié)構(gòu)逼近
    3.1 極小反例中點和邊的性質(zhì)
    3.2 極小反例中圈的結(jié)構(gòu)
第四章 對于主定理的證明
附錄
參考文獻
致謝
攻讀學位期間發(fā)表的學術(shù)論文
學位論文評閱及答辯情況表



本文編號：3152616