如果一個圖G的點集可以被劃分為k個獨立集,那么該圖G是k-可正常著色的,即使得圖G中的相鄰兩點著不同的顏色。如果給圖G=（V,E）的每一個頂點v一個顏色列表L（v）,對于圖G的每一個頂點v,G都存在一個正常著色c使得c（v）∈L（v）,稱圖G=（V,E）是L-可著色的。如果圖G的每一個頂點v的顏色列表集|L（v）|≥k,對于圖G的每一個頂點v,圖G都存在一個正常著色c使得c（v）∈L（v）,那么圖G是k-可選的。本文主要研究平面圖的DP-著色。作為列表染色的推廣,也就是DP-著色,是由Devorak和Postle在2018年提出來的。對于列表染色來說,把著相同顏色的相鄰點對之間進行匹配,但對于DP-著色來說,相鄰點對之間的匹配是可以任意給的。平面圖中有一部分關于列表著色的結論可以推廣到DP-著色,但是大部分的列表著色的結論是不可以推廣到DP-著色的。正如Bernshteyn和Kostochka指出:DP-著色和列表著色是不同的。因此將許多學者和興趣愛好者的目光從列表染色轉移到DP-著色上是一個很自然的事情。由于已經(jīng)證明了每個可平面圖是DP-5-可著色的,那么能不能把色數(shù)的界給降一點呢?... 

【文章來源】：華中師范大學湖北省 211工程院校 教育部直屬院校

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

【學位級別】：碩士

【部分圖文】：

圖１：?一些圖結構??

領士學位論文??ＭＡＳＴＥＲ＇Ｓ?ＴＨＥＳＩＳ??ｋＶ??＼?／?＞—／?＼—ｆｆ?＼—ｙ??／—ｖ?／—＼?／—）—ｖ??７＾＾??（１）?（２）?（３）?（４）??圖５：壞的４〇－面的相關結構閣??｜?＋?２ｘ＊?＋?２ｘｉ?＋?２ｘｉ＞０。如果相鄰的都是５＋－點時，比較壞的情況是以下兩種情??況：圖⑶中的４－點都變成５＋－點，那么此時有２ｘｉ＞４ｘ＾故０，圖⑷中??的４－點都是５＋－點，那么此時有／／（ｒ）２／ｘ（ｒ）?＋?２ｘ｜＋２ｘ！?＋?２ｘｉ２〇。如果圖（３）中??的?４？點有一個是?５＋－點，／／（７１）?２＂（Ｔ）?＋?２ｘ｜＋２ｘ！?＋?２ｘｉ?＋?ｌｘ｜?之?０，如果圖（４）??中的４－點有一個是５＋－點，那么此時有／／（ｒ）?２／Ｉ（ｒ）＋２ｘ｜?＋?２ｘｉ?＋?２ｘ忐＋?２ｘ｜?２〇，??或者是圖（５）的情況，／／（ｒ）?＞?＂（ｒ）?＋?２ｘｆ?＋?２ｘ?長＋?ｌｘ?忐＋?２ｘ｜＋ｌｘ?士?２?０。??情形４?４ｃｒ面上相鄰３個４＋－點時，則至少相鄰１個１０＋－面，由／？⑴和／？⑷，??＞?ｆｉ｛Ｔ）?＋?ｌｘ＾?＋?ｌｘｉ?＋?ｌｘｉ＞０〇??情形５?知－面上相鄰４個４＋－點時，由權轉移規(guī)則，有／ｉ＇（ｒ）２〇。?□??引理４．３．如果：Ｔ是壞的４〇－面和它上面的１０個頂點導出的子圖，那么壞的??知－面和其上所有頂點導出的子圖的最小最終權值在５－面上各有一個４－點且該４－點??不與４〇－面上的點相鄰時取得，且／／（ｒ）?２?０。??證明：由引理３．２的（１）、（７）和（８），壞的４０－面至少存在２個４＋－點且不在??同一個５－面上。當壞的４〇－面上的４＋－點都是４－點的

碩士學位論文??ＭＡＳＴＥＲ’Ｓ?ＴＨＥＳＩＳ??ｉ?－ｔ?；—？’?ｘｉ—?？?＾?？?？?ｔ??ｔ＝ｎ?口：?］?：：?：?ｒａ?ｒａ：??ｙ?９?Ｗ＇＼?ｑ??？?？?？?—ｒｖ?—？?？?？??—ｆｈ￣￣？￣￣－ｔ?ｔ￣￣ｔ——？?－ｆ￣￣ｆ?？，?￣ｉ?ｆ?ｆ￣?ｆ＾??Ｘｍ?．１－４—３．?ｉ—ｍ??？???ｆ——ｔ——ｆ??ｒ：】??圖６：?ｌ?－?５－面的相關結構圖??３－點，只會增加不會減少；所以有當壞的４Ｃ－面上出現(xiàn)２個４－點、出現(xiàn)２個５＋－點??或者出現(xiàn)１個４－點和１個５＋－點的是情況是糟糕的。下面我們就這三種情況進行討??論：??情形１當壞的４〇－面上出現(xiàn)２個４－點的時候，５－面上各有一個４－點且該４－點不與??４〇－面上的點相鄰時是最壞的，此時ｆ（ｒ）?２?／ｉ（ｒ）?＋?Ｓｘ｜＋４ｘｆ?＋?４ｘ吉２（）。??情形２當壞的４〇－面上出現(xiàn)２個５＋－點的時候，５－面上各有一個５＋－點且該５＋－點不??與４。－面上的點相鄰時是最壞的，此時／Ａ：Ｔ）仝ｍＣＯ?＋?８ｘ｜?＋?４ｘｆ?＋?２ｘｉ＞０。??情形３當壞的４Ｑ－面上出現(xiàn)１個４－點和１個５＋－點的時候，５－面上各有一個??４－點和５＋－點且該４－點和５＋－點不與４０－面上的點相鄰時是最壞的，此時／／（乃２??＂（Ｔ）?＋?８ｘ｜?＋?４ｘ．?＋?ｌｘ｜?＋?２ｘ咅仝０。而且我們還可以得到，這三種情形下，??情形〗是最終權值最小的一個，且不低于〇。?口??弓丨理４．４．如果：Ｔ是Ｉ?—?５－面和它上面的８個頂點導出的子圖，則Ｗ）?２?〇。??證明：由引理３．４的（１）、（２）、（３）和（４），?４！?—?５－面至


本文編號：3496816