一类图的色唯一性

Chromatic uniqueness of a class graphs

如果两个图的色多项式相等,称这两个图色等价。如果与一个图色等价的所有图都与这个图同构,称这个图色唯一。类似的,如果两个图的伴随多项式相等,称这两个图伴随等价。如果与一个图伴随等价的所有图都与这个图同构,称这个图伴随唯一。众所周知,两个图色等价当且仅当它们的补图伴随等价;一个图色唯一当且仅当它的补图伴随唯一。给出了一类图伴随唯一的一个充分必要条件,因而给出了它的补图色唯一的一个充分必要条件。

Two graphs are chromatically equivalent if they have the same chromatic polynomials. A graph is said to be chromati- cally unique if each graph which has same chromatic polynomial is isomorphic with it. Similarly, two graphs are adjointly equiv- alent if they have the same adjoint polynomials. A graph is said to be adjointly unique if each graph which has same adjoint poly- nomial is isomorphic with it. As we all know, two graphs are chromatically equivalent if their complement are adjointly equivalent; a graph is chromatically unique if its complement is adjointly unique. In this paper, a necessary and sufficient condition of a classe graphs adjointly unique is given, thus a necessary and sufficient condition of their complement chromatically unique is given.