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

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

【共引文獻】

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

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

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

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

，

本文編號：368178