平面圖的邊列表染色和線(xiàn)性染色.pdf

1、一個(gè)有序?qū)=(V,E)稱(chēng)為一個(gè)無(wú)向圖,其中V是一個(gè)有限集合,E是V中的不同元素的無(wú)序?qū)Φ募?V中的元素叫做圖G的頂點(diǎn),E中的元素叫做圖G的邊.通常用V(G),E(G)分別表示圖G的頂點(diǎn)集合與邊集合.沒(méi)有重邊和環(huán)的圖叫做簡(jiǎn)單圖.
　　 圖G的一個(gè)k-邊染色是一個(gè)映射φ:E(G)→{1,2,…,k},其中k是整數(shù).若映射φ還滿(mǎn)足對(duì)于G中的每一對(duì)相鄰邊e和e′,有φ(e)≠φ(e′),則稱(chēng)這個(gè)k-邊染色是正常的.如果G有一個(gè)正常的

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

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

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