图正常着色的最大方法数.doc

图正常着色的最大方法数
闵照翠 黄 刚 杨建国 [摘要] 本文在前人研究图正常着色的最大方法数基础上,更好地给出了色多项式界的控制,使得结论的研究更具有普遍意义.
[关键词] 正常着色 最大方法数 色多项式

图正常着色的最大方法数
闵照翠 黄 刚 杨建国 [摘要] 本文在前人研究图正常着色的最大方法数基础上,更好地给出了色多项式界的控制,使得结论的研究更具有普遍意义.
[关键词] 正常着色 最大方法数 色多项式

一、引言
图的色多项式是Birkhoff 为攻克4色问题而于1912年提出来的,Brikhoff 与Lewis 对图的色多项式进行了更为深入的研究. 虽然到目前为止,用这种方法并没有解决4 色问题,但图的色多项式对图论的理论及其应用都具有很大的影响..
定义图G的一个正常k顶点着色,简称图的k点着色,用k种颜色对G的各顶点进行着色,使得任意相邻的两点着不同的颜色. 若G至少有一个正常k点着色,就称G是正常k点可着色的. 使G是k点可着色的数k的最小值称为图G的色数, 记为. 若,,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个连通分支,记为.