發(fā)布時(shí)間：2017-05-15 15:28

  本文關(guān)鍵詞：平面圖的非正常染色，由筆耕文化傳播整理發(fā)布。

【摘要】：本文研究的圖是有限,簡(jiǎn)單,無(wú)向圖.設(shè)G=(V, E)是一個(gè)圖,k是一個(gè)正整數(shù).若存在一個(gè)映射Φ:V→{1,2…,k)滿足：對(duì)任意xy∈E,都有Φ(x)≠Φ(y),則稱φ是G的一個(gè)k-染色,此時(shí)我們稱G是k-可染的.給G的每個(gè)頂點(diǎn)v分配一個(gè)顏色集合L(v),則稱L={L(υ)|υ∈V}是G的一個(gè)色列表.若對(duì)任意的點(diǎn)v∈V,都能從其相應(yīng)的色列表L(v)中選取一個(gè)顏色φ(v)染給v,使得Aυυ∈E(G),有Φ(υ)≠Φ(υ),則稱G是L-可染的.若G對(duì)任意一個(gè)滿足|L(v)|≥k的色列表L,G都是L-可染的,則稱G是k-列表可染的,也稱G是k-可選擇的. 設(shè)di,i∈{1,2,...,k}是k個(gè)非負(fù)整數(shù).若能用1,2,…,k這k種顏色對(duì)圖G=(V,E)的點(diǎn)進(jìn)行染色,使得染顏色i的點(diǎn)組成的點(diǎn)導(dǎo)出子圖G[Vi]的最大度至多為di,i∈{1,2...,k},則稱G是非正常(d1,d2,…,dk)-可染的,或簡(jiǎn)稱(d1,d2,…,dk)-可染的.若d1=d2=…=dk=d,則稱G是d-非正常k-可染的,或稱(k,d)*-可染的.設(shè)d是一個(gè)非負(fù)整數(shù),L是G的一個(gè)色列表.若對(duì)每一個(gè)L={L(υ)|υ∈V,|L(υ)|≥k},我們都能用L(v)中的一種顏色去染v,使得染顏色i的點(diǎn)組成的點(diǎn)導(dǎo)出子圖G[Vi]的最大度至多為d,則稱G是非正常(k,d)*-可選的,或簡(jiǎn)稱(k,d)*-可選的. 易知,正常染色是非正常染色的特例,非正常染色是正常染色的推廣. 1976年,Steinberg提出了一個(gè)猜想：既不含4-圈又不含5-圈的可平面圖是3-可染的.由于解決著名的Steinberg猜想有很大的難度,Erdos提出這樣的一個(gè)問(wèn)題：尋找一個(gè)常數(shù)C,使得不含4到C-圈的可平面圖是3-可染的. 本論文分為四章,主要圍繞以上猜想和問(wèn)題展開(kāi)研究,所得結(jié)論改進(jìn)了現(xiàn)有的一些結(jié)果.第一章介紹了本論文所涉及的有關(guān)定義,并對(duì)正常染色和非正常染色的研究現(xiàn)狀做了一個(gè)綜述.第二章主要討論既不含4-圈又不含5-圈的可平面圖的非正常染色,第三章主要討論既不含4-圈又不含6-圈的可平面圖的非正常染色.第四章主要討論不含4-圈的可平面圖的非正常列表染色.
【關(guān)鍵詞】：可平面圖 非正常染色 圈 權(quán)轉(zhuǎn)移
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：O157.5
【目錄】：

• 摘要3-5
• ABSTRACT5-7
• 目錄7-8
• 1 緒論8-14
• 1.1 基本概念8-10
• 1.2 非正常染色的研究概況10-13
• 1.3 本文的主要結(jié)果13-14
• 2 既不含4-圈又不含5-圈的可平面圖的非正常染色14-35
• 2.1 既不含4-圈又不含5-圈的可平面圖是(1,1,0)-可染的14-28
• 2.2 既不含4-圈又不含5-圈的可平面圖是(3,0,0)-可染的28-35
• 3 既不含4-圈又不含6-圈的可平面圖的非正常染色35-46
• 3.1 既不含4-圈又不含6-圈的可平面圖是(1,1,0)-可染的35-41
• 3.2 既不含4-圈又不含6-圈的可平面圖是(3,0,0)-可染的41-46
• 4 不含4-圈的可平面圖的非正常列表染色46-54
• 參考文獻(xiàn)54-58
• 在學(xué)期間的研究成果及發(fā)表的論文58-59
• 致謝59-62

【共引文獻(xiàn)】

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

1 王應(yīng)前;金利剛;亢瑩利;;沒(méi)有4至6-圈的平面圖是(1,0,0)-可染的[J];中國(guó)科學(xué):數(shù)學(xué);2013年11期

2 趙春紅;蔡宇澤;;一類不含5-圈平面圖結(jié)構(gòu)的幾個(gè)結(jié)論[J];沙洲職業(yè)工學(xué)院學(xué)報(bào);2013年02期

  本文關(guān)鍵詞：平面圖的非正常染色，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：368178