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

[關(guān)鍵詞] 正常著色 最大方法數(shù) 色多項(xiàng)式

一、引言

圖的色多項(xiàng)式是Birkhoff 為攻克4色問(wèn)題而于1912年提出來(lái)的，Brikhoff 與Lewis 對(duì)圖的色多項(xiàng)式進(jìn)行了更為深入的研究. 雖然到目前為止，用這種方法并沒(méi)有解決4 色問(wèn)題，但圖的色多項(xiàng)式對(duì)圖論的理論及其應(yīng)用都具有很大的影響..

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

色多項(xiàng)式的研究及其應(yīng)用非常廣泛，也有很多關(guān)于色多項(xiàng)式的研究成果，首先，對(duì)任意圖的色多項(xiàng)式求解就是一個(gè)非常困難的問(wèn)題，目前人們?cè)谶@方面的研究也就停留在對(duì)一些特殊圖色多項(xiàng)式的求解上，目前有很多學(xué)者在色等價(jià)性和色唯一性上做一些研究，研究色多項(xiàng)式系數(shù)之和的文章也有很多，還有一部分是專注于色多項(xiàng)式的系數(shù)與圖本身的結(jié)構(gòu)之間的關(guān)系，研究方法也形形色色，有的技巧性很強(qiáng)，有的學(xué)者會(huì)利用容斥原理來(lái)研究色多項(xiàng)式，與色多項(xiàng)式關(guān)聯(lián)的部分也會(huì)很多.

二、定理證明

設(shè)G(V，E)是一個(gè)無(wú)向簡(jiǎn)單的標(biāo)定圖，并且，用f(G，t)表示G的正常t-著色的方法數(shù)（即色多項(xiàng)式）.又設(shè)是具有n個(gè)頂點(diǎn)，m條邊無(wú)向的標(biāo)定圖的集合，用表示中圖的正常t-著色的最大方法數(shù).

即

文獻(xiàn)中給出了的上界為:

文獻(xiàn) 中給出了當(dāng)時(shí)，有

由上述文獻(xiàn)中的結(jié)論不難證明下述引理1和引理2.

引理1:若a，b是正整數(shù)，正整數(shù)，則有

引理2：若是n個(gè)正整數(shù)，正整數(shù)則

成立.

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

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

成立

證明：記

因?yàn)?，，而是一連通圖且為可t-著色的.

故由引理3有

所以，又由引理2知

成立.

所以引理4得證.

引理5：設(shè)且可t-著色的，有k個(gè)連通枝，

則.

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

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

由引理5色多項(xiàng)式，所以有

所以

通過(guò)對(duì)諸多問(wèn)題的分析，可以看出在時(shí)即各分支的頂點(diǎn)個(gè)數(shù)相等時(shí)我們控制的最好.

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

參考文獻(xiàn)

[1]徐志宏 許三星 圖的色多項(xiàng)式系數(shù)與圖的特征關(guān)系[J].雁北師范學(xué)院學(xué)報(bào).2006(10):15-17.

[2]徐利民 圖的正常著色的最大方法數(shù)[J] 淮南職業(yè)技術(shù)學(xué)院學(xué)報(bào).Vol.2，Serial No.5