本文關(guān)鍵詞：圖的2-距離染色

  更多相關(guān)文章： 2-距離染色 圈 最大度 平面圖

【摘要】：本文主要研究有限無向圖.圖G的k-2-距離染色是指映射c：V(G)→{1,2,…,k},使得對G中滿足0dG(u,v)≤2的點對u,v有c(u)≠c(u)稱x2(G)=min{k|G有一個k-2-距離染色}為G的2-距離色數(shù). 圖G的一個列表配置L是指給G的每個頂點v∈V(G)分配一個可用色集L(v).設(shè)L是G的一個列表配置,若G的一個2-距離染色c對任意的v∈V滿足c(v)∈L(v),則稱c是G的一個L-2-距離染色.若對G的任意一個滿足|L(v)|≥k的列表配置L,G都有一個L-2-距離染色,則稱G是2-距離k-可選的,并稱x2l(G)=min{k|G是2-距離k-可選的}為G的2-距離列表色數(shù). 關(guān)于平面圖的2-距離染色,1977年,Wegner提出了如下的一個猜想：對平面圖G,若△(G)=3,則x2(G)≤7；若4≤△(G)≤7,則x2(G)≤△(G)+5；若△(G)≥8,則x2(G)≤[3/2；△(G)]+1. 本文分為三章,主要研究了不含特殊短圈的平面圖和最大度小于等于5的圖的2-距離染色.第一章介紹了一些基礎(chǔ)定義和2-距離染色的研究現(xiàn)狀,并給出了本文的主要結(jié)果.第二章主要研究了不含特殊短圈的平面圖的2-距離染色.證明了：(1)若G是不含3-,4-,8-圈且△(G)≥14的平面圖,則x2(G)≤△(G)+5.(2)若G是不含3-,5-圈和相交4-圈且△(G)≥12的平面圖,則x2l(G)≤△+6.第三章主要研究了最大度小于等于5的圖的2-距離染色.證明了：(1)若圖G滿足△(G)≤5且mod(G)18/7,則x2l(G)≤7.(2)若平面圖G滿足△(G)≤5,則下列結(jié)論成立：1)若g(G)≥5,則x2l(G)≤13；2)若g(G)≥6,則x2l(G)≤11；3)若g(G)≥7,則x2l(G)≤9；4)若g(G)≥8,則x2l(G)≤8.
【關(guān)鍵詞】：2-距離染色 圈 最大度 平面圖
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：O157.5
【目錄】：

• 摘要3-4
• ABSTRACT4-6
• 目錄6-7
• 1 緒論7-13
• 1.1 基本概念7-8
• 1.2 2-距離染色的研究概況8-12
• 1.3 本文的主要結(jié)果12-13
• 2 不含特殊短圈的平面圖13-39
• 2.1 不含3-,4-,8-圈的平面圖13-27
• 2.2 不含3-,5-圈和相交4-圈的平面圖27-39
• 3 最大度小于等于5的圖39-58
• 3.1 △(G)≤5且mad(G)<18/739-44
• 3.2 △(G)≤5的平面圖44-58
• 參考文獻58-61
• 在學(xué)期間的研究成果及發(fā)表的論文61-62
• 致謝62-64

【參考文獻】

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

1 謝朝宗;;馬斯內(nèi)版《瑪儂》:大都會舞臺上盡顯巴黎社交生活[J];歌劇;2012年05期

，

本文編號：614429