关于色多项式的若干注记

Notes on Chromatic Polynomial

给出若干类型多项式为简单图的色多项式的充分必要条件、连通图和连通双分图的色多项式必须满足的条件,研究图及其补图的色多项式对图特征的描述程度,并提出若干值得进一步探讨的问题。

In this paper, the author gives the necessary and sufficient condition under which several types of polynomials are the chromatic polynomials of simple graphs, and the condi- tion that the chromatic polynomials of connected graphs and connected bigraphs must satis- fy; and considers the extent to which the chromatic polynomials of graph and its complement describe the characteristic of graph; and finally, proposes some questions worthy of further inquiry.