几类图色等价的充分必要条件

Necessary and Sufficient Conditions for Some Classes of Special Graphs Being Chromatic Equivalent

在微积分罗尔定理理论基础上,运用归纳法证明了两个多项式恒等的一个充分条件,进而利用色数、围长、补图的理想子图数给出了两类图n+s(s,n∈Z+)阶n-色图色等价的充分必要条件,这为构造色等价图提供了新方法,由此得到几类新的色等价的n+3阶n-色图.

On the basis of Rolle＇s theorem in the calculus, a sufficient condition for two polynomials being equivalent was proved. Furthermore, the necessary and sufficient conditions for two n-colorable graphs of order n＋s（s,nE Z＋） being chromatic equivalent was given by chromatic number, girth and subgraph number of complement graph. The conclusion provided new approaches for constructing chromatic equivalent graphs. Then by these new methods, some new classes of chromatic equivalent n colorable graphs of order n＋3 were obtained.