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

本文編號：2623929