色多项式系数的一点注记

本文将讨论简单图,以n和m分别表示图G的点数和边数。文中不加说明的术语和记号可参阅[1]。G的顶点着色,是对G的顶点分配颜色,使邻接的顶点有不同的颜色。同一种颜色的顶点的全体组成的集合,称为G的一个色类,以m_r(G)表示将G的顶点集分成Υ个色类的不同分划数,定义多项式为图G的色多项式。显然,当m>0时,m_1(G)=0为方便起见,今后讨论的图G均假定m>0。Whitney(1932)得到如下的着名结果(参见[1],P.69)。