本文關鍵詞：若干圖的邊染色和全染色

  更多相關文章： 邊染色 全染色 平面圖 廣義Mycielski圖

【摘要】：圖G的κ-邊染色就是從邊集合E(G)到顏色集合{1,2,…,κ}的一個映射,使得相鄰的邊得到不同的顏色.圖G的邊色數(shù)χ'(G)就是最小的κ,使得圖G有一個正常k-邊染色.圖G的κ-全染色就是從點邊集合V(G)u E(G)到顏色集合{1,2,…,κ}的一個映射,使得相鄰的邊得到不同的顏色,相鄰的點得到不同的顏色,關聯(lián)的點和邊得到不同的顏色.圖G的全色數(shù)χ'(G)就是最小的κ,使得圖G有一個κ-全染色.本文研究了若干圖的邊染色和全染色問題,包括廣義Mycielski圖、3-正則圖、1-平面圖、平面圖和奇圖,主要圍繞平面圖邊染色猜想,列表邊染色猜想,全染色猜想和唯一最大度點全染色猜想,力求能給這些猜想提供更有力的證據(jù).本學位論文共分三章.在第一章中,我們首先給出本文所需要的基本概念,然后介紹若干圖的邊染色和全染色的研究現(xiàn)狀,最后呈現(xiàn)本文的主要結果.在第二章中,我們研究若干圖的邊染色.(1)刻畫了廣義Mycielski圖的邊色數(shù);(2)考慮平面圖的分數(shù)邊色數(shù),并且證明了3-正則圖是(7,2)-邊可染的,推進了Fulkerson猜想和Mohar猜想;(3)研究最大度點導出子圖條件下的1-平面圖和平面圖的邊染色和列表邊染色問題.在第三章中,我們研究若干圖的全染色.(1)證明了廣義Mycielski圖滿足全染色猜想,并且給出類型1的若干充分條件；(2)研究最大度點導出子圖條件下的1-平面圖和平面圖的全染色和列表全染色問題；(3)證明了奇圖K(2κ+1,κ)滿足全染色猜想.
【關鍵詞】：邊染色 全染色 平面圖 廣義Mycielski圖
【學位授予單位】：浙江師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-4
• Abstract4-8
• 第一章 緒論8-14
• 1.1 基本概念8-9
• 1.2 邊染色研究概況9-11
• 1.3 全染色研究概況11-12
• 1.4 本文主要結果12-14
• 第二章 若干圖的邊染色14-32
• 2.1 廣義Mycileski圖的邊色數(shù)14-17
• 2.2 平面圖和3-正則圖的分數(shù)邊色數(shù)17-27
• 2.2.1 平面圖的分數(shù)邊色數(shù)17-21
• 2.2.2 3-正則圖的分數(shù)邊色數(shù)21-27
• 2.3 稀疏最大度點的圖的邊色數(shù)和邊選擇數(shù)27-32
• 2.3.1 1-平面圖的邊色數(shù)27-28
• 2.3.2 平面圖的邊選擇數(shù)28-32
• 第三章 若干圖的全染色32-44
• 3.1 廣義Mycielski圖的全色數(shù)32-36
• 3.2 稀疏最大度點的圖的全色數(shù)和全選擇數(shù)36-41
• 3.2.1 1-平面圖的全色數(shù)36-37
• 3.2.2 平面圖的全選擇數(shù)37-41
• 3.3 奇圖的全色數(shù)41-44
• 參考文獻44-48
• 攻讀學位期間取得的研究成果48-50
• 致謝50-54
• 學位論文誠信承諾書54

【相似文獻】

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

1 王淑棟,龐善臣;系列平行圖的邊色數(shù)[J];山東科技大學學報(自然科學版);2002年02期

2 牟海波;串圖的邊色數(shù)[J];蘭州鐵道學院學報;2003年03期

3 田雙亮;若干n重積圖的點可區(qū)別邊色數(shù)[J];西北民族大學學報(自然科學版);2005年02期

4 尹志剛;費旭云;李曉彪;何建新;;關于圖的圓邊色數(shù)幾個重要定理[J];高師理科學刊;2011年04期

5 王艷麗;苗連英;;圖的集合邊色數(shù)[J];山東大學學報(理學版);2012年06期

6 賈振聲;何滿年;張忠輔;;關于圖的3—邊色數(shù)[J];太原重型機械學院學報;1992年01期

7 卓新建;邊色數(shù)為Δ的一個充分條件[J];曲阜師范大學學報(自然科學版);1995年04期

8 劉二根;廣義圖K(5,n)的邊色數(shù)[J];華東交通大學學報;1997年02期

9 田雙亮,張忠輔;積圖鄰強邊色數(shù)的注記[J];蘭州交通大學學報;2005年03期

10 瞿曉鴻;;一個特殊圖形的邊色數(shù)[J];昆明理工大學學報(理工版);2006年02期

中國重要會議論文全文數(shù)據(jù)庫 前4條

1 劉華;趙鵬;馬明;冶建華;張忠輔;;圖S_m*F_n的鄰點可區(qū)別的邊色數(shù)[A];中國運籌學會第七屆學術交流會論文集（中卷）[C];2004年

2 包世堂;;關于C_m懔C_n的邊色數(shù)[A];中國運籌學會第七屆學術交流會論文集（上卷）[C];2004年

3 趙傳成;;關于C_m·S_n和C_mΔSn的邊色數(shù)[A];中國運籌學會第七屆學術交流會論文集（中卷）[C];2004年

4 馬剛;;S_m∨F_n的全色數(shù)和點可區(qū)別邊色數(shù)[A];中國運籌學會第九屆學術交流會論文集[C];2008年

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

1 高毓平;圖的邊染色及一些有限制條件的染色[D];山東大學;2016年

2 賀丹;圖的距離邊標號及其相關問題[D];東南大學;2015年

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

1 郭振香;對具有大圍長可平面圖強邊色數(shù)的研究[D];河南大學;2015年

2 楊燦權;若干圖的邊染色和全染色[D];浙江師范大學;2015年

3 楊海珍;一些圖的圓邊色數(shù)[D];首都師范大學;2008年

4 章文超;圖的貪婪博弈邊色數(shù)和游戲邊色數(shù)[D];浙江師范大學;2014年

5 毛新葉;圖的點可區(qū)別邊染色的一些結果[D];西北師范大學;2009年

6 劉利群;圖的D（2）-點可區(qū)別及點可區(qū)別正常邊染色[D];西北師范大學;2007年

7 田京京;圖的D（β）-點可區(qū)別邊染色及其概率方法[D];西北師范大學;2007年

8 楊玉紅;若干圖類的星邊染色[D];西北師范大學;2009年

9 鄧凱;圖的星邊染色[D];西北師范大學;2007年

10 薄朝升;星著色和強邊著色的研究[D];重慶大學;2011年

，

本文編號：553290