染色是圖論的一個(gè)重要分支,而圖論這門學(xué)科最初誕生于著名的哥尼斯堡七橋問題,以圖為研究對(duì)象.圖的染色問題一直是圖論界的一個(gè)熱門話題,它起源于1852年由Guthrie提出的“四色猜想”.隨著圖論這門學(xué)科的發(fā)展,后來Vizing提出了點(diǎn)染色的列表形式,列表點(diǎn)染色是點(diǎn)染色的推廣.2015年,Dvo?ák和Postle提出了關(guān)于列表點(diǎn)染色的一般形式,簡稱為DP-染色.在這之前及其期間,還有一些其他的染色被陸續(xù)提出來,比如圖的點(diǎn)蔭度問題,圖的退化問題,等等.2018年,T.Wang提出了關(guān)于圖的嚴(yán)格f-退化染色問題,簡稱為SFDT.嚴(yán)格f-退化染色是以上所有染色的更一般形式,這具有很大的研究意義.通過研究點(diǎn)蔭度,DP-染色和退化問題的相關(guān)論文,來更好的學(xué)習(xí)和研究圖的SFDT問題.能否把圖的相關(guān)染色推廣到SFDT上,及圖G是否有一個(gè)SFDT是一個(gè)值得研究的問題.本論文主要研究平面圖及環(huán)面圖的嚴(yán)格f-退化染色問題,分為五個(gè)章節(jié).第一章是一些基本術(shù)語及符號(hào)定義,還有一些相關(guān)的定理.第二章給出了與嚴(yán)格f-退化染色相關(guān)的結(jié)論.第三章我們給出的結(jié)果是沒有一些小的子圖的環(huán)面圖有一個(gè)嚴(yán)格f-退化染色,它是許多已... 

【文章來源】：河南大學(xué)河南省

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

定理2.2.2里的遞歸點(diǎn)對(duì)

另一個(gè)可約結(jié)構(gòu)

平面圖有一個(gè)嚴(yán)格f-退化染色的一些充分條件μ′(v)≥64232×133×215>0.因此，v不能是任何4-正則的5-面的懸掛點(diǎn).根據(jù)引理3.2.3，v不可能同時(shí)給剩余三個(gè)鄰接5+-面權(quán)23，所以μ′(v)>643×23=0.情形7.設(shè)v是一個(gè)7+-點(diǎn).根據(jù)給權(quán)規(guī)則，v平均給每個(gè)鄰接的面權(quán)最多13，因此μ′(v)≥d(v)4d(v)×13>0.圖3.3:情形8里的一些子情形情形8.設(shè)v是一個(gè)5-點(diǎn)，那么▽(v)≤3.如果▽(v)=3且f1,f2和f4都是3-面，那么f3和f5都是6+-面，因此v最多分別給f3和f5權(quán)13，通過f4-面給出去權(quán)215，因此μ′(v)=542152×13>0.如果v鄰接兩個(gè)3-面f1和f2，那么f3和f5一定都是6+-面，因此μ′(v)=54>0.如果▽(v)=1，那么μ′(v)=542152×13>0.如果▽(v)=0，那么μ′(v)=54>0.接下來，假設(shè)v鄰接兩個(gè)不相鄰的3-面，不妨假設(shè)是f1和f3.情形8.1.假設(shè)f2不是一個(gè)F5-面.那么很容易推出f2是一個(gè)5-面最多相鄰四個(gè)3-面，或者5-面上有至少兩個(gè)5+-鄰點(diǎn)，或者是一個(gè)6+-面.根據(jù)規(guī)則R4和R5，v最多給f2權(quán)13.如果v5是一個(gè)5+-點(diǎn)，那么v最多分別給f4和f5權(quán)16，因此μ′(v)≥54132×162×215>0.如果v5是一個(gè)4-點(diǎn)，那么f4或者f5是一個(gè)-面，因此μ′(v)≥542×132×215>0.情形8.2.假設(shè)f2是一個(gè)F5-面.根據(jù)引理3.3.1，v不可能是任何一個(gè)4-正則的5-面的懸掛點(diǎn).根據(jù)引理3.2.1，f4和f5都不可能是（5，4，4，4，4）-面.情形8.2.1.v5是一個(gè)4-點(diǎn)，那么f4或者f5是一個(gè)-面，不然就會(huì)出現(xiàn)圖1.2(b)禁止的結(jié)構(gòu)，矛盾.當(dāng)f4或者f5是一個(gè)-面時(shí)，v是不給它權(quán)的.如果v給了f4或者f5一個(gè)正權(quán)，那么這個(gè)面一定是一個(gè)5-面且至少有兩個(gè)5+-鄰點(diǎn)，那么v最多給f4或者f5權(quán)4312=16，因此μ′(v)≥542316>0.18


本文編號(hào)：3248116