A note on graph colorings and graph polynomials (Q1369660): Difference between revisions

Given a graph \(G\), form a polynomial \(\prod (x_i-x_j)\) where the product is over all edges \((i,j)\) with \(i < j\). If \(G\) is not \(k\)-colourable, then no matter how the variables \(x_i\) are assigned integers from \(1\) to \(k\) the polynomial is zero. Hence the graph polynomial encodes chromatic properties of the graph. In particular, if a graph has chromatic number exceeding \(k\), then its polynomial lies in an ideal generated by the polynomials of complete graphs of order \(k+1\). In this paper the authors give a short proof of this relation between the chromatic number and the ideal generated by complete graphs. Their proof uses a version of Hajós' theorem formulated by Ore. As corollaries, they get results of Alon and Tarsi and of Kleitman and Lovász.