A note on graph colorings and graph polynomials
type: Item
instance of: scholarly article
title: A note on graph colorings and graph polynomials
zbMATH Open document ID: 0883.05050
author: Noga Alon
author: Michael Tarsi
published in: Journal of Combinatorial Theory. Series B
publication date: 1998-02-22T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1076879
zbMATH Keywords: graph polynomial
zbMATH Keywords: chromatic number
zbMATH Keywords: complete graphs
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
OpenAlex ID: W1988564791
cites work: Colorings and orientations of graphs
cites work: Q4857375
cites work: Bounding the Independence Number of a Graph
cites work: Q5528475
DOI: 10.1006/JCTB.1997.1753
description: scientific article; zbMATH DE number 1076879