A note on graph colorings and graph polynomials (Q1369660)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A note on graph colorings and graph polynomials
scientific article

    Statements

    A note on graph colorings and graph polynomials (English)
    0 references
    0 references
    0 references
    22 February 1998
    0 references
    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.
    0 references
    graph polynomial
    0 references
    chromatic number
    0 references
    complete graphs
    0 references

    Identifiers