圖正常著色的最大方法數

[摘要] 本文在前人研究圖正常著色的最大方法數基礎上，更好地給出了色多項式界的控制，使得結論的研究更具有普遍意義.

[關鍵詞] 正常著色 最大方法數 色多項式

一、引言

圖的色多項式是Birkhoff 為攻克4色問題而于1912年提出來的，Brikhoff 與Lewis 對圖的色多項式進行了更為深入的研究. 雖然到目前為止，用這種方法并沒有解決4 色問題，但圖的色多項式對圖論的理論及其應用都具有很大的影響..

定義圖G的一個正常k頂點著色，簡稱圖的k點著色，用k種顏色對G的各頂點進行著色，使得任意相鄰的兩點著不同的顏色. 若G至少有一個正常k點著色，就稱G是正常k點可著色的. 使G是k點可著色的數k的最小值稱為圖G的色數， 記為. 若，則稱G為k色圖.圖G的一個至多t色的著色是G的一個t種或不到t種顏色的著色，G的兩種著色方案中若至少有一個頂點指定為不同的顏色就認為是兩種不同的著色方法. 我們用f(G，t)表示標定圖G的不同的至多t可著色的數目. 一般地講，對于給定的P階標定圖G，對其進行t正常染色的方法數是t的一個函數，它可表示成t的一個多項式，稱為圖的色多項式，記為f(G，t).

色多項式的研究及其應用非常廣泛，也有很多關于色多項式的研究成果，首先，對任意圖的色多項式求解就是一個非常困難的問題，目前人們在這方面的研究也就停留在對一些特殊圖色多項式的求解上，目前有很多學者在色等價性和色唯一性上做一些研究，研究色多項式系數之和的文章也有很多，還有一部分是專注于色多項式的系數與圖本身的結構之間的關系，研究方法也形形色色，有的技巧性很強，有的學者會利用容斥原理來研究色多項式，與色多項式關聯的部分也會很多.

二、定理證明

設G(V，E)是一個無向簡單的標定圖，并且，用f(G，t)表示G的正常t-著色的方法數（即色多項式）.又設是具有n個頂點，m條邊無向的標定圖的集合，用表示中圖的正常t-著色的最大方法數.

即

文獻中給出了的上界為:

文獻 中給出了當時，有

由上述文獻中的結論不難證明下述引理1和引理2.

引理1:若a，b是正整數，正整數，則有

引理2：若是n個正整數，正整數則

成立.

引理3:設連通圖且是可t-著色的，則.

引理4:設，且是可t-著色的，不妨設G有k個連通分支，記為.令，則有

成立

證明：記

因為，，而是一連通圖且為可t-著色的.

故由引理3有

所以，又由引理2知

成立.

所以引理4得證.

引理5：設且可t-著色的，有k個連通枝，

則.

定理:設，且是可t-著色的，不妨設G有k個連通分支，記為.令，則有下面結論成立：

證明：設，若G是不可t-著色的，則，若G是可t-著色的，由引理4有

由引理5色多項式，所以有

所以

通過對諸多問題的分析，可以看出在時即各分支的頂點個數相等時我們控制的最好.

從定理結論可以看出，此定理內容要比已有結論好出很多，它們都是以上定理的一小部分，結論也更加準確許多.

參考文獻

[1]徐志宏 許三星 圖的色多項式系數與圖的特征關系[J].雁北師范學院學報.2006(10):15-17.

[2]徐利民 圖的正常著色的最大方法數[J] 淮南職業技術學院學報.Vol.2，Serial No.5