A Note on Graph Colorings and Graph Polynomials

It is known that the chromatic number of a graphG=(V, E) withV={1, 2, …, n} exceedskiff the graph polynomialfG=∑ij∈E, i<j (xi−xj) lies in certain ideals. We describe a short proof of this result, using Oreʹs version of Hajósʹ theorem. We also show that a certain weighted sum over the properk-colorings of a graph can be computed from its graph polynomial in a simple manner.