發(fā)布時(shí)間：2017-11-03 07:13

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

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

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

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

【相似文獻(xiàn)】

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

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

2 ;[J];;年期

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

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

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

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

本文編號(hào)：1135157