平面圖的r-hued染色.pdf

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

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

3、d染色，圖G的r-hued染色數(shù),記作Xr(G).是使圖G存在( k,r)染色的最小的k值. r-hued染色是圖的點染色的推廣.
　　本學位論文主要研究了圍長至少為5的平面圖的r-hued染色以及一般平面圖的3-hued染色.
　　第一章介紹研究領域的相關發(fā)展背景,研究現(xiàn)狀和本文所要用到的基本概念.
　　第二章證明了圍長至少為5的平面圖的r-hued染色的相關結(jié)果：當3≤r≤7時,且圖G是圍長至少為5的平面圖,則Xr