一些圖的圓邊染色.pdf

1、本文考慮的圖若無特殊聲明均為簡單圖。一個簡單圖的k可邊染色是一個從含k種顏色的色集到圖G的邊集合的映射，并且使得相鄰兩邊染不同的顏色。對于一個k可邊染色的圖G來說，最小的k就是圖G的邊色數(shù)。Vince提出了圖的圓染色的概念，圖的圓邊染色就是圖的圓染色由點到邊的推廣。圖G是一個圖，正整數(shù)k，d滿足2d≤k，那么圖的(k，d)邊染色是指從顏色集{0，1，…，k-1}到圖G的邊的映射c，并且任意相鄰的兩邊e1，e2滿足d≤｜c(e1)-c(e

2、2)｜≤k-d。圖G的圓邊染色數(shù)x'c(G)就是圖G含有(k，d)邊染色中的k/d比值的下界。即：χ'c(G)=inf{k/d：G含有一個(k，d)邊染色}。 圖的圓邊染色的許多基本性質(zhì)被Hackmann證明： 定理0.1 [3]如果G是一個含有q條邊的圖，那么χ'c(G)=min{k/d：G含有一個(k，d)邊染色且k≤q)。 定理0.2 [3]如果G是第一類圖，那么χ'c(G)=△(G)。 如果G是第

3、二類圖，那么△(G)<χ'c(C)≤△(G)+1。 定理0.3 [3]如果圖G是第二類圖，那么要么χ'c(G)=△(G)+1要么△(G)+1/α'(G)≤χ'c(G)≤△(G)+α'(G)-1/α'(G)(其中α'(G)是圖G的邊獨立數(shù))第一類圖的圓邊染色問題已經(jīng)解決，而許多第二類圖的圓邊染色問題沒有得以解決。所以本文研究的主要是一些第二類圖的圓邊染色性質(zhì)。由于這個問題是一個NP問題，所以本文的思想就是確定某第二類圖的范圍。而確

4、定Χlc(G)，就要從定義出發(fā)，找尋(k，d)染色。找出上述范圍的k1，k2，k3，…，kn，dl，…，dn，uG=k1/d1/>k2/d2>…>kn/dn=lG，檢驗圖G是否含有(k2，d2)染色，如果沒有，Χlc(G)=k1/d1；如果含有(k2，d2)染色，繼續(xù)檢驗(k3，d3)染色，依次類推。本文根據(jù)以上算法來確定一些圖的圓邊染色。全文共分四章，第一章介紹圖論的一些基本概念，并給出圖的染色理論的已有定理證明及圓邊染色的理論。第二

5、章介紹解決圓邊染色的算法。 第三章我們給出了頂點數(shù)小于7的所有第二類圖的圓邊染色數(shù)。主要結(jié)論有： 定理0.4 在頂點小于7的所有第二類圖中，其圓邊染色數(shù)： Χlc(G1)=3，Χlc(G2)=5/2，Χlc(G3)=4，Χlc(G4)=9/2，Χlc(G5)=5，Χlc(G6)=4，Χlc(G7)=5，Χlc(G8)=5。 定理0.5 如果G是一個C3×C3的笛卡爾積圖，那么其圓邊色數(shù)為： Χlc