圖的染色問題在圖論及理論計算機科學中都有著極為廣泛的應(yīng)用,是圖論研究中最重要的課題之一.在本論文中,我們研究圖的邊染色及一些簡單圖的有限制條件的染色.設(shè)G是可能具有重邊但不具有環(huán)的圖,分別用V,E,△和μ表示G的頂點集,邊集,最大度和重數(shù).本文的第一章給出圖的邊染色,點染色及其它一些有限制條件的染色的定義,并給出相關(guān)問題的一些主要研究進展和猜想.圖的邊染色的核心問題是確定其邊色數(shù).圖G的k-邊染色φ是從E到集合{1,2,…,k}（其中的元素稱為顏色）的一個映射,使得任意兩條相鄰邊的顏色不同.G的邊色數(shù)是使得G存在k-邊染色的最小正整數(shù)k,記作χ’與研究邊染色相比,研究分數(shù)邊染色更加容易一些.圖G的分數(shù)邊染色是G的匹配的集合M（G）的一個非負賦權(quán)ω（.）,使得對每條邊e∈E,有∑M∈M:e∈Mw（M）=1顯然這樣的賦權(quán)ω（.）存在.G的所有分數(shù)邊染色中最小的總權(quán)值∑m∈Mw（M）稱為是G的分數(shù)邊色數(shù),記作χ’f,計算χ’f是多項式時間的.圖G的邊色數(shù)與分數(shù)邊色數(shù)的關(guān)系如下△≤x’f ≤x’≤△+μ,其中的上界為Vizing的一個經(jīng)典結(jié)果.事實上,如果χ’f>△,那么x’f=max|... 

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

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

【學位級別】：博士

【部分圖文】：

圖５．３：斷言５．２．３的說明??


本文編號：3278770