一个点并路的补图的色等价图类

The Chromatic Equivalence Classes of the Complements of Union Graphs of Vertex and a Path

设G是一个n阶图.众所周知,两个图G和H色等价当且仅当它们的补图伴随等价.可见伴随多项式是研究图的色多项式的一种有效途径.本文通过比较伴随多项式的最小根,最终计算了K_(1)∪P_(m)的伴随等价图的个数以及它的伴随等价图类.进一步,计算了K_(1)∪P_(m)的色等价图的个数以及它的色等价图类,这里K_(1)和P_(m)分别表示一个孤立点和m个点的路.

Let G be a graph with order n.It is well known that two graphs G and H are chromatically equivalent if and only if their complementary graphs are adjoint equivalencet.It can be seen that adjoint polynomials are an effective way to study the chromatic polynomials of graphs.By comparing the minimum roots of adjoint polynomials,this paper finally calculates the number of adjoint equivalent graphs of K_(1)∪P_(m) and the class of adjoint equivalent graphs are also calculated.Furthermore,the number of chromatic equivalent graphs of K_(1)∪P_(m) and the class of chromatic equivalent graphs of K_(1)∪P_(m) are also calculated.Here,K_(1) and P_(m) represent an isolated vertex and a path of m vertices,respectively.