圖的著色問題一直以來是圖論的熱門經(jīng)典問題.它最早起源于著名的“四色問題”,已廣泛應(yīng)用于信息論,計(jì)算機(jī)科學(xué)及人工智能等多個(gè)領(lǐng)域.本文研究了平面圖的DP-著色以及圖的密接性質(zhì),這主要屬于四色問題的延伸范疇.全文共分八章,主要內(nèi)容如下:在第一章,我們首先給出了文中所需的一些基本概念和符號,接著分別介紹了本文后續(xù)各個(gè)章節(jié)中所涉及的研究問題及背景.在第二章,我們介紹了 Borodin在1996年的一個(gè)有關(guān)列表著色的猜想:所有不含4到8-圈的平面圖是3-可選的.Dvorak和Postle在2017年引入DP-著色的全新概念解決了這一長達(dá)20年的猜想,我們在這一結(jié)果的基礎(chǔ)上做出改進(jìn),證明了不含圈長至多為8的相鄰圈的平面圖是3-可選的.在第三章,基于第二章的研究技巧,我們利用DP-著色試圖解決平面圖三色領(lǐng)域的相關(guān)熱門問題.我們研究了平面圖的DP-3-著色問題.我們把原先平面圖在列表著色中的結(jié)果推廣到了 DP-著色.我們通過構(gòu)造一個(gè)“近-(k-1)-退化”的子圖來解決在這一推廣中所遇到的麻煩.在第四章,我們在第三章中給出的結(jié)果的基礎(chǔ)上,進(jìn)一步研究了不含{4,a,b,9}-圈的平面圖,這里5≤α≠b≤8....

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

【學(xué)位級別】：博士

【部分圖文】：

圖１：在一個(gè)不含７－圈的平面圖中所有可能的族？??

３－面就稱作ｆｃ－簇．下面是一個(gè)由??不同的點(diǎn)組成的所有可能的簇在一個(gè)不含７－圈的平面圖中（在［１８］中，給出了所有??在這樣平面圖中的２３個(gè)族）．??Ａ?？菜図：翁擇??（１）?１－ｃｌｕｓｔｅｒ?（２）?２－ｃｌｕｓｔｅｒ?（３）?３－ｃｌｕｓｔｅｒ?（４）?４－ｃｌｕｓｔｅ....

圖４：?一個(gè)４－圈不是ＤＰ－２－可著色的：左邊是一個(gè)４－圈Ｇ，右邊是圖扎．??

?本章我們完成對定理１．３．２的證明．我們主要運(yùn)用權(quán)轉(zhuǎn)移的方法，這個(gè)方法基??于強(qiáng)的歸納法．如果一個(gè)結(jié)構(gòu)不能出現(xiàn)在一個(gè)最小反例Ｇ中，稱這個(gè)結(jié)構(gòu)是可約??的．我們可以很快的發(fā)現(xiàn)定理１．３．１中的所有證明都依賴于下列事實(shí)：一個(gè)只含??三度點(diǎn)的偶圈是可約的．換句話說，如果Ｃ？是一個(gè)所相....

圖５：—個(gè)１０－圈包含一條３－控制的特殊（３，４，３）－路，一條特殊的（４，４，４，３）－路，和??

？博士學(xué)位論文??ＤＯＣＴＯＲＡＬ?ＤＩＳＳＥＲＴＡＴＩＯＮ??圖５：—個(gè)１０－圈包含一條３－控制的特殊（３，４，３）－路，一條特殊的（４，４，４，３）－路，和??一條極大的（３，４，３）－路，它不是特殊的但用其中的兩個(gè)點(diǎn)可以組成一條特殊的??（４，３）－路．??引理３．１．３．....

圖６：前兩個(gè)是特殊１０－面（第二張圖里／上的４－點(diǎn)也可能在其它位置），中間三個(gè)??１０－一１０－．??

博士學(xué)位論文??ｙ?ＤＯＣＴＯＲＡＬ．?ＤＩＳＳＥＲＴＡＴＩＯＮ??ｓｐｅｃｉａｌ?ｐｏｏｒ?ｂａｄ??圖６：前兩個(gè)是特殊１０－面（第二張圖里／上的４－點(diǎn)也可能在其它位置），中間三個(gè)??是窮１０－面，最后一個(gè)是壞１０－面．??—如果ｄ（ｔ＞）?２?６，那么ｗ給／譽(yù)．??（Ｒ３ｂ）....

本文編號：3900649