圖論是數(shù)學(xué)的一個(gè)分支,是近年來發(fā)展迅速而又應(yīng)用廣泛的一門學(xué)科.染色問題是圖論中十分活躍的研究課題,有著深刻而豐富理論結(jié)果和廣泛的實(shí)際應(yīng)用,其理論和方法在離散數(shù)學(xué)中占有重要地位.本文證明了不含5-圈與6-圈相鄰的平面圖是DP-4-可著色的,并且還證明了每個(gè)不含相交5-圈的平面圖是DP-4-可著色的.具體內(nèi)容包括:·第一章介紹論文的研究背景、研究意義、國內(nèi)外學(xué)者對(duì)這方面的研究狀況,以及一些相關(guān)引理和本文需要證明的定理.通過對(duì)研究背景及研究現(xiàn)狀的深入分析,充分說明了本文研究工作的必要性和創(chuàng)新點(diǎn).·第二章介紹本文涉及到的基本概念和符號(hào).·第三章為了證明定理1.3,本章節(jié)證明了更強(qiáng)的結(jié)果,見定理3.1,然后用定理3.1來證明定理1.3.假設(shè)(G,C0)是定理3.1的最小反例,其|V(G)|最小,此處C0是圖G中的預(yù)著色k-圈,其中k=3,4.如果C0是一個(gè)分離圈,則C0的任何預(yù)著色可以分別延拓到int(C0)和ext(Co).然后得到了圖G的一個(gè)DP-4-著色,得出矛盾.本章節(jié)研究了最小反例圖G的一些結(jié)構(gòu)特征,找到并證明圖G不存在的可約構(gòu)形.然后根據(jù)找到的可約構(gòu)形制定恰當(dāng)?shù)臋?quán)轉(zhuǎn)移規(guī)則,用權(quán)轉(zhuǎn)移規(guī)...

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

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

【文章目錄】：
摘要
Abstract
第一章 引言
    1.1 研究背景、研究意義及國內(nèi)外研究成果
    1.2 本文主要結(jié)果和相關(guān)結(jié)論
第二章 預(yù)備知識(shí)
第三章 定理1.3的證明
    3.1 壞4-圈的介紹
    3.2 定理1.3的證明
    3.3 最小反例的結(jié)構(gòu)性質(zhì)
    3.4 權(quán)轉(zhuǎn)移規(guī)則
    3.5 檢查權(quán)轉(zhuǎn)移后圖(G,C₀)所有點(diǎn)和面的權(quán)
第四章 定理1.4的證明
    4.1 定理1.4的證明
    4.2 最小反例的結(jié)構(gòu)性質(zhì)
    4.3 權(quán)轉(zhuǎn)移規(guī)則
    4.4 檢查權(quán)轉(zhuǎn)移后圖(G,C₀)所有點(diǎn)和面的權(quán)
第五章 總結(jié)展望
參考文獻(xiàn)
致謝



本文編號(hào)：3736033