關(guān)于一些特殊圖及其聯(lián)圖的全色數(shù).pdf

1、圖論（Graph Theory）是離散數(shù)學最重要的一個分支，它以由若干給定的點和連接兩點之間的線構(gòu)成的圖為研究對象，用以描述某些事物之間的聯(lián)系。而染色問題是圖論的重要問題之一。為了恰當?shù)乇硎狙芯空n題中各元素之間的關(guān)系，作為一種可行的工具，人們引入了圖的染色理論．
　　 全染色的概念是對點染色和邊染色的推廣，它要求把圖的所有元素（頂點和邊）都染色時，任意相鄰或關(guān)聯(lián)的元素染色不同。全染色是圖論染色的一個傳統(tǒng)問題，由Vizing(19

2、64)和Behzad(1965)各自獨立提出，同時他們分別給出全染色猜想：對于任何一個簡單圖G，△(G)十1≤Xr(G)≤△(G)+2。其中△(G)是圖G的最大度，Xr(G)表示G的全色數(shù)。由于對于任何一個圖G，△(G)+1≤Xr(G)都成立，因而顯然下界是恒成立的，我們把滿足Xr(G)=△(G)+1的圖稱為是第一類的，把滿足Xr(G)=△（G)+2的圖稱為是第二類的。
　　 本文就此探討了關(guān)于圖的全染色問題，第一章從歷史的角度