【摘要】：圖的劃分問題是指將圖的頂點(diǎn)集按特定要求劃分成點(diǎn)子集.經(jīng)典的圖染色問題是將圖的頂點(diǎn)集劃分成獨(dú)立點(diǎn)集,而最大割問題則是尋求不同集合之間的邊數(shù)達(dá)到最大的劃分.我們主要研究的是兩類劃分問題,一類是圖的染色問題,另一類則是公平劃分問題.近年來,圖染色問題被廣泛研究.第二章主要研究1-可平面圖的邊染色問題.1-可平面圖是指可被嵌入到平面中使得每條邊被其余至多一條邊穿過的圖.該圖類是由Ringle首次引入.著名的Vizing邊染色定理表明每個(gè)圖都滿足邊色數(shù)等于△或者△ +1,分別對(duì)應(yīng)第一類圖和第二類圖.張欣和吳建良[79]證明了當(dāng)△(G)≥ 10時(shí),任何1-可平面圖都滿足邊色數(shù)等于△(G).當(dāng)最大度至多為9時(shí),已得到在一些限制條件下的1-可平面圖是第一類的:(1)[81]不含弦5-圈且△ ≥ 9,或者(2)[82]不含相鄰三角形且△ ≥ 8,或者(3)[78]不含三角形且△ ≥ 7.最近,張欣[80]構(gòu)造了包含相鄰三角形且最大度為6或7的第二類1-可平面圖.在第二章,我們證明了不含相交三角形和弦5-圈且最大度為7的1-可平面圖是第一類的.在第三章,我們考慮了可平面圖的列表染色問題.給圖G的每個(gè)頂點(diǎn)v一個(gè)顏色集合L(v),形成圖G的一個(gè)列表分派L.給定圖G 一個(gè)列表分派L,每個(gè)元素u ∈ V從其所分派顏色集合L(v)中選取顏色的正常染色,就是圖G的一個(gè)L-染色.若任意給定的列表分派L且每個(gè)u ∈ V的顏色集合都有|L(v)|≥ k,圖G都有一個(gè)L-染色,則稱圖G是k-可選色的.滿足圖G是k-可選色的最小k值,是圖G的列表染色數(shù)或選色數(shù),記作χlist(G).Thomassen[56]證明了所有可平面圖都是5-可選的,[57]還證明了所有不含3-圈和4-圈的可平面圖是3-可選的.Voigt[63]找出一個(gè)非4-可選的可平面圖,和一個(gè)列表色數(shù)為4的不含三角形的可平面圖[64].她[65]還構(gòu)造了一個(gè)不含4圈和5圈的非3-可選的可平面圖,所以著名的Steinberg猜想不能推廣至3-可選的情形.Montassier等人[49]證明了任一5--圈的距離至少為4的可平面圖是3-可選的.他們[48]也證明了若不含4-圈和5-圈且d%，

本文編號(hào)：2623929