本文關(guān)鍵詞：平面圖的r-hued染色

  更多相關(guān)文章： 平面圖 極小反例 差值轉(zhuǎn)移 勒貝格公式

【摘要】：一個(gè)有序?qū)=(V, E)稱為一個(gè)無向圖,其中V和E通常是有限集合.V中的元素稱為圖G的頂點(diǎn),E是由V中不同元素的無序?qū)M成的集合,E中的元素稱為圖G的邊.我們通常用V(G)和E(G)來表示圖G的頂點(diǎn)集和邊集.一個(gè)圖G稱為是平面的當(dāng)且僅當(dāng)它可以畫在平面上,使得它的任何一條邊不與另外一條邊交叉.對(duì)于正整數(shù)k,r.令k={1,2,…k}.如果c:V(G)→k,V'(?)V(G),那么c(V')={c(v)|u∈V')圖G的(k,r)染色是這樣一個(gè)映射c:V(G)→k,滿足下列兩個(gè)條件：(C1)對(duì)于每條邊uv∈E(G),c(u)≠c(v);(C2)對(duì)于每個(gè)點(diǎn)v∈V(G),|c(NG(v))|≥min{dG(v),r}.條件(C2)經(jīng)常被作為r-hued條件.對(duì)于整數(shù)k,r0,圖G的(k,r)染色是一個(gè)正常k染色,使得對(duì)于每一個(gè)度數(shù)為d(v)的點(diǎn)v,v至少表現(xiàn)min{d(u),r}種顏色,這樣的染色,我們稱之為r-hued染色,圖G的r-hued染色數(shù),記作Xr(G).是使圖G存在(k,r)染色的最小的k值r-hued染色是圖的點(diǎn)染色的推廣本學(xué)位論文主要研究了圍長(zhǎng)至少為5的平面圖的r-hued染色以及一般平面圖的3-hued染色.第一章,介紹研究領(lǐng)域的相關(guān)發(fā)展背景,研究現(xiàn)狀和本文所要用到的基本概念.第二章,證明了圍長(zhǎng)至少為5的平面圖的r-hued染色的相關(guān)結(jié)果：當(dāng)3≤r≤7時(shí),且圖G是圍長(zhǎng)至少為5的平面圖,則x,(G)≤r+11特別的,當(dāng)r=3,4,5,6時(shí),分別有x3(G)≤10,x4(G)≤11,x5(G)≤12,x6(G)≤13.第三章,給出了一般平面圖的3-hued染色的結(jié)果,即若圖G是一個(gè)平面圖,則X3(G)≤12.第四章,對(duì)本文的研究結(jié)果作了簡(jiǎn)單的總結(jié)并做了進(jìn)一步的展望.
【關(guān)鍵詞】：平面圖 極小反例 差值轉(zhuǎn)移 勒貝格公式
【學(xué)位授予單位】：中國(guó)礦業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5
【目錄】：

• 致謝4-5
• 摘要5-6
• Abstract6-10
• 變量注釋表10-11
• 1 緒論11-15
• 1.1 研究背景11-12
• 1.2 基本概念12
• 1.3 研究現(xiàn)狀12-15
• 2 圍長(zhǎng)至少為5的平面圖的r-hued染色15-27
• 2.1 幾個(gè)結(jié)構(gòu)引理15-24
• 2.2 主要結(jié)果24-27
• 3 一般平面圖的3-hued染色27-33
• 3.1 主要結(jié)果28-33
• 4 總結(jié)與展望33-34
• 參考文獻(xiàn)34-37
• 作者簡(jiǎn)歷37-40
• 學(xué)位論文數(shù)據(jù)集40

【相似文獻(xiàn)】

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

1 李衛(wèi)奇;平面圖的r-hued染色[D];中國(guó)礦業(yè)大學(xué);2016年

，

本文編號(hào)：999459