平面圖的r-hued染色.pdf

1、一個(gè)有序?qū)=(V,E)稱為一個(gè)無(wú)向圖，其中V和E通常是有限集合.V中的元素稱為圖G的頂點(diǎn),E是由V中不同元素的無(wú)序?qū)M成的集合,E中的元素稱為圖G的邊.通常用V(G)和E(G)來(lái)表示圖G的頂點(diǎn)集和邊集.一個(gè)圖G稱為是平面的當(dāng)且僅當(dāng)它可以畫在平面上,使得它的任何一條邊不與另外一條邊交叉.
　　對(duì)于正整數(shù)k, r.令k={1,2,…k}.如果 c:V(G)→k, V'CV(G),那么c(V')={c(υ)|υ∈ V'}.圖G的(k,

2、r)染色是這樣一個(gè)映射c:V(G)→k,滿足下列兩個(gè)條件：
　　(C1)對(duì)于每條邊uυ∈E(G), c(u)= c(υ);
　　(C2)對(duì)于每個(gè)點(diǎn)υ∈V(G),|c(NG(∈))|≥min{dG(v), r}.
　　條件(C2)經(jīng)常被作為r-hued條件.對(duì)于整數(shù)k,r>0,圖G的(k, r)染色是一個(gè)正常k染色,使得對(duì)于每一個(gè)度數(shù)為d(v)的點(diǎn)v, v至少表現(xiàn)min{d(v),r)種顏色,這樣的染色,稱之為r-hue

3、d染色，圖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的平面圖,則Xr