超圖的頂點(diǎn)著色.pdf

1、超圖是普通圖的推廣，普通圖的著色在圖論中占有重要地位?，F(xiàn)已形成著色理論。而超圖的著色作為普通圖的著色的推廣，其研究意義自然更加深刻，內(nèi)容更加豐富，適用范圍自然更為廣泛。這篇文章主要研究了超圖的著色并獲得了一些相關(guān)結(jié)果。
　　 第一部分介紹了與本文有關(guān)的基本概念及其為什么要研究圖和超圖的著色問(wèn)題。從而說(shuō)明研究超圖的著色是有重要意義的。
　　 第二部分研究了超圖的多項(xiàng)式與著色的關(guān)系，用超圖的多項(xiàng)式刻畫(huà)了超圖的著色。特別對(duì)超圖

2、的2-色多項(xiàng)式進(jìn)行了具體研究。并且得到了判斷一個(gè)超圖不能2-著色的充要條件及可以2-著色的充分條件。接著又對(duì)邊數(shù)等于頂點(diǎn)數(shù)的超圖進(jìn)行了研究，得到了可以2-著色的充分條件。最后由本文定義的多項(xiàng)式得到了一般超圖色數(shù)的一個(gè)上界。
　　 第三部分研究了超圖的著色與Lovász引理的關(guān)系，我們利用Lovász局部引理給出超圖可以t-著色的一個(gè)充分條件以及對(duì)其進(jìn)行t-著色使得每種顏色在每條邊中均出現(xiàn)的充分條件。接著給出了對(duì)超圖進(jìn)行2-著色使