圖的邊染色與列表邊染色.pdf

1、圖的染色理論是圖論中最重要的分支之一，在無線通訊頻道分配、艦隊維護、任務分派、交通定向等諸多領域都有著廣泛的應用。本文主要研究圖的邊染色與列表邊染色。 在第二章中，給出第一類平面圖的若干充分條件，證明下列兩個結論: (1)△(G)=6，且不含弦5-圈的平面圖G是第一類； (2)△(G)=5且不含相交三角形的平面圖G是第一類。 在第三章中，從平面圖推廣到歐拉特征值非負的一般曲面上，從而改進了卜月華和王維凡在

2、文獻[4]中的結論，證明:對于△(G)=6，且χ(∑)≥0的圖G滿足下列條件之一，則G是第一類： (1)不含相鄰三角形； (2)不含弦5-圈和弦6-圈。 在第四章中，研究了平面圖G的列表邊染色，并證明如下兩個結論: (1)若G是一個△(G)≠5，且不含弦5-圈的平面圖，那么G是(△(G)+1)-邊可選的。 (2)若平面圖G滿足下列條件之一，則G是(△(G)+1)-邊可選的： (a)不含弦4