论文研究 一类图的色唯一性.pdf

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