2-連通外平面圖的r-hued染色和不含鄰接三角形的1-平面圖的無圈邊染色.pdf

1、一個(gè)有序?qū)=(V,E)稱為一個(gè)無向圖，其中V和E一般是有限集.V中的元素稱為圖G的頂點(diǎn)，E是由V中不同元素的無序?qū)M成的集合，E中的元素稱為圖G的邊.通常用V(G)和E(G)來表示圖G的頂點(diǎn)集和邊集.把沒有環(huán)和重邊的圖稱為簡(jiǎn)單圖.若無特別說明，本論文研究的圖均是指簡(jiǎn)單的有限無向圖.
　　一個(gè)平面圖G如果有一個(gè)平面嵌入使得它所有頂點(diǎn)都在某個(gè)面上,這樣的圖被稱作外平面圖.一個(gè)圖G是1-平面的當(dāng)且僅當(dāng)它可以畫在一個(gè)平面上，使得它的任何

2、一條邊最多交叉另外一條邊.G的(k,r)-染色是指G的一個(gè)映射c:V(G)→k,同時(shí)滿足以下兩個(gè)條件：
　　(a)對(duì)每條邊υυ∈E(G),有c(u)=c(υ).
　　(b)對(duì)每個(gè)頂點(diǎn)υ∈V(G),有|c(NG(υ))|>min{dc(υ),r].
　　G的無圈k-邊染色是指圖G的一個(gè)不產(chǎn)生二色圈的正常k-邊染色.圖G的無圈邊色數(shù)x'a(G)是使得圖G是無圈k-邊可染的最小正整數(shù)k.
　　本學(xué)術(shù)論文主要研究：階p≥

3、2的2-連通外平面圖的r-hued染色及r-hued列表染色以及不含鄰接三角形的1-平面圖的無圈邊染色.
　　第1章主要介紹了本論文的研究領(lǐng)域及背景,所用到的基本概念及研究現(xiàn)狀.
　　第2章主要證明了階p≥2的2-連通外平面圖的r-hued染色及r-hued列表染色的結(jié)果：
　　(i)Xr(G)≤f(r)
　　(ii)XL,r(G)≤fr)+1.
　　我們定義：(此處公式省略)
　　第3章主要研究了不