圖論是現(xiàn)代數(shù)學的重要分支之一,圖論研究的熱點和難點問題是圖染色問題,它起源于著名的“四色定理”,即給平面上的任何一張地圖著色,使得有公共邊界的國家所染顏色不同且最多使用四種顏色.本文研究的圖是有限,簡單,無向圖.設(shè)G=（V,E）是一個圖,kk是一個正整數(shù).若存在一個映射φ:V → {1,2,...k}滿足:對任意xy ∈E,有φ（x）≠（y）,則稱φ是G的個k個染色,此時我們稱G是k是可染的的這種染色我們稱之為圖G的正常染色.設(shè)d₁,d₂,...d_k是k個非負整數(shù),若圖G=（V,E）的頂點集V能被剖分成k個子集V1,V2,...Vk使得對任意的i=1,2,...,k,Vi的點導出子圖G[Vi]的最大度至多為di,則稱圖G是非正常（d₁,d₂,...d_k）-可染的,或簡稱為（d₁,d₂,…d_k）-可染的.若d₁=d₂ =…=d_k... 

【文章來源】：山東師范大學山東省

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

【學位級別】：碩士

【文章目錄】：
中文摘要
英文摘要
第一章 引言
    §1.1 基本概念與符號
    §1.2 圖的非正常染色的歷史和研究現(xiàn)狀
    §1.3 本文的主要結(jié)果
第二章 平面圖的（3,0,0）-染色
    §2.1 預(yù)備知識
    §2.2 平面圖的（3,0,0）-可染的可約構(gòu)型
第三章 不含4-圈和弦6-圈的平面圖是（3,0,0）-可染的
    §3.1 預(yù)備知識
    §3.2 不含4-圈和弦6-圈的平面圖是（3,0,0）-可染的
第四章 可進一步研究的問題
參考文獻
攻讀學位期間發(fā)表或提交的學術(shù)論文
致謝


【參考文獻】：
期刊論文
[1]沒有4至6-圈的平面圖是（1,0,0）-可染的[J]. 王應(yīng)前,金利剛,亢瑩利.  中國科學:數(shù)學. 2013(11)
[2]既不含4-圈又不含6-圈的平面圖的非正常染色[J]. 徐靈姬,王應(yīng)前.  中國科學:數(shù)學. 2013(01)
[3]Planar graphs without 4,6,8-cycles are 3-colorable[J]. Wei-fan WANG~+ Min CHEN Department of Mathematics,Zhejiang Normal University,Jinhua 321004,China.  Science in China（Series A:Mathematics）. 2007(11)

碩士論文
[1]不含相鄰三角形和6圈的平面圖的（3，1，0）著色[D]. 葉詩蓉.華中師范大學 2015



本文編號：3091225