平面圖的邊列表染色和線性染色.pdf

1、一個有序對G=(V,E)稱為一個無向圖,其中V是一個有限集合,E是V中的不同元素的無序對的集合.V中的元素叫做圖G的頂點,E中的元素叫做圖G的邊.通常用V(G),E(G)分別表示圖G的頂點集合與邊集合.沒有重邊和環(huán)的圖叫做簡單圖.
　　 圖G的一個k-邊染色是一個映射φ:E(G)→{1,2,…,k},其中k是整數.若映射φ還滿足對于G中的每一對相鄰邊e和e′,有φ(e)≠φ(e′),則稱這個k-邊染色是正常的.如果G有一個正常的

2、k-邊染色,則稱G是k-邊可染的.G的邊色數x′(G)是使得G是k-邊可染的最小的整數,稱L為圖G的一個邊列表,如果它給每條邊e∈G,一個顏色集合L(e),若有一個正常的邊染色φ,使得每一條邊e滿足φ(e)∈L(e)則稱G是L-邊可染的,或稱φ是G的一個L-邊染色.如果對任意表L和每條邊e∈E(G),都有｜L(e)｜≥k,且G是L-邊可染的,則稱G是k-邊可選的.G的邊列表色數x′l(G)是使得G是k-邊可選擇的最小的非負整數k.類似地

3、可定義單獨染頂點和同時染頂點和邊的G的點列表色數xl(G)和全列表色數x"l(G).由定義可直接得到x′'(G)≥x′(G)≥△(G)和x"l(G)≥x"(G)≥△(G)+1.
　　 如果圖G的一個正常頂點染色c滿足染任意兩種顏色的頂點集合導出的子圖是一個線性森林,即一些點不交的路的并,則稱這個正常點染色c為圖G的線性染色.圖G的線性色數,是指圖G的所有線性染色中使用的最少顏色的個數,用lc(G)表示.
　　 本文主要討

4、論平面圖的邊列表染色和線性染色問題.對前人的一些研究結果進行改進和補充.
　　 在第一章中,給出本文所用到的基本概念,介紹相關領域的背景和研究現狀,呈現本文的主要結果.
　　 第二章中,主要證明了關于平面圖的邊列表染色的研究結果:最大度為6且不含4-圈和7-圈的平面圖是△-邊可選的,(△+1)-全可選的；最大度為5且不含4,6,8-圈的平面圖是△-邊可選的,(△+1)-全可選的.
　　 第三章中證明了關于平面圖的