本文關(guān)鍵詞：平面圖的非正常著色

  更多相關(guān)文章： 平面圖 非正常著色 圈 權(quán)轉(zhuǎn)移

【摘要】：設(shè)G=(V，，E)是簡單平面圖,c_1,c_2...,c_k是k個非負整數(shù).若圖G的頂點集V能被劃分成k個子集V_1，V_2,...,V_k,使得對任意的i,1≤i≤k,導(dǎo)出子圖G[Vi]]的最大度至多為ci,則稱圖G是(c_1,c_2...,c_k)-可著色的.圖的著色問題的研究來源于著名的四色問題,歷來是圖論界的熱點也是難點.我們知道確定一個平面圖是否是3-可著色的是NP-完備的.1959年,Grotzsch提出了一個著名的定理每一個不含三角形的平面圖是3-可著色的.因此許多學(xué)者致力于尋找一個允許存在三角形的平面圖是3-可著色的充分條件.1976年,Steinberg提出猜想不含4-圈和5-圈的平面圖是(0,0,0)-可著色的.Xu和Wang證明了不含4-圈和6-圈的平面圖是(1,1,0)-可著色的,本文在這一結(jié)論的基礎(chǔ)上進一步改進,我們證明任何一個3-圈和4-圈不相鄰及無6-圈的平面圖是(1,1,0)-可著色的.論文的組織結(jié)構(gòu)如下.·第一章介紹了論文的研究背景以及本文解決的問題.·第二章介紹了本文涉及到的基本概念及符號.·第三章給出了圖G的可約結(jié)構(gòu).·第四章給出了權(quán)轉(zhuǎn)移規(guī)則.·第五章給出了圖G的點,面最終權(quán)值的驗證.
【關(guān)鍵詞】：平面圖 非正常著色 圈 權(quán)轉(zhuǎn)移
【學(xué)位授予單位】：華中師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要5-6
• Abstract6-8
• 第一章 引言8-10
• 第二章 預(yù)備知識10-12
• 第三章 圖G的可約結(jié)構(gòu)12-19
• 第四章 權(quán)轉(zhuǎn)移規(guī)則19-20
• 第五章 最終權(quán)值的驗證20-25
• 參考文獻25-27
• 致謝27

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前2條

1 徐利民;圖的正常著色的最大方法數(shù)[J];淮南職業(yè)技術(shù)學(xué)院學(xué)報;2002年04期

2 ;[J];;年期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 馬建清;圖的處處非零3-流、Z_3-連通性以及著色問題的研究[D];華中師范大學(xué);2015年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 白鷹;平面圖的非正常著色[D];華中師范大學(xué);2016年

本文編號：1135157