點(diǎn)染色是指顏色集對(duì)圖G中各個(gè)頂點(diǎn)的一種分配,使得任意兩個(gè)相鄰的頂點(diǎn)被染上不同的顏色.隨著四色定理的產(chǎn)生與發(fā)展,人們定義了多種多樣的非正常染色方法,如列表染色.近來(lái),Dvorak和Postle又介紹了一種新的染色方法——DP-染色,它可以看作是列表染色的一種推廣.DP-染色的實(shí)質(zhì)是將每個(gè)點(diǎn)變?yōu)閳F(tuán)數(shù)為顏色列表數(shù)的團(tuán),再對(duì)相鄰的點(diǎn)進(jìn)行任意匹配,最后找出其中的獨(dú)立集.雖然不是所有的列表染色都能推廣到DP-染色,例如偶圈,但DP-染色仍然是一種有效的研究方法.事實(shí)上已經(jīng)有很多列表染色的結(jié)論被推廣到DP-染色上了,其中較為著名的有:不含3-圈,4-圈的平面圖是DP-3-可染的.人們對(duì)于DP-3-可染的平面圖的充分條件十分感興趣.本文則主要證明了以下兩個(gè)定理:(1)不含4-,6-圈,且不含相鄰5-圈,三角形距離dΔ≥ 3的平面圖是DP-3-可染的.(2)不含5-,6-圈,且4-圈距離d□≥3,三角形距離dΔ≥ 3的平面圖是DP-3-可染的.本文研究方法為首先假設(shè)存在滿足定理?xiàng)l件的最小反例,研究最小反例的結(jié)構(gòu)特點(diǎn),然后對(duì)其點(diǎn)和面進(jìn)行賦權(quán),再制定權(quán)轉(zhuǎn)移規(guī)則,通過(guò)權(quán)轉(zhuǎn)移過(guò)程和的不變性得到矛盾,從而說(shuō)明這樣...

【文章頁(yè)數(shù)】：28 頁(yè)

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

【文章目錄】：
摘要
Abstract
第一章 序論
第二章 可約結(jié)構(gòu)
第三章 定理1.4的證明
    3.1 最小反例的結(jié)構(gòu)特點(diǎn)
    3.2 權(quán)轉(zhuǎn)移過(guò)程
第四章 定理1.5的證明
    4.1 最小反例的結(jié)構(gòu)特點(diǎn)
    4.2 權(quán)轉(zhuǎn)移過(guò)程
第五章 研究展望
參考文獻(xiàn)
致謝



本文編號(hào)：3797560