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

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

【學位級別】：碩士

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



本文編號：3736033