×

zbMATH — the first resource for mathematics

The stipulation polynomial of a uniquely list-colorable graph. (English) Zbl 0826.05025
Given a simple graph \(G\) of order \(n\) and a set \(S= (S_1,\dots, S_n)\) of lists of colors at the vertices of \(G\), it is said that \(G\) is \(S\) list-colorable if there is a proper coloring of \(G\) such that each vertex \(i\) receives a color from \(S_i\). N. Alon and M. Tarsi [Combinatorica 12, No. 2, 125-134 (1992; Zbl 0756.05049)] showed that \(G\) is \(S\) list-colorable if and only if its graph polynomial \[ f_G({\mathbf x}):= \prod_{i\sim j} (x_i- x_j) \] does not lie in the ideal \(I\) generated by the annihilator polynomials \(g_i({\mathbf x})\) of the colors available at the vertices. The present authors study the case where \(G\) is uniquely list-colorable and determine the irreducible factors of the remainder (or stipulation) polynomial \(\overline f_G= f_G\pmod I\). They establish a bijection between the factors of \(\overline f_G\) and the edges of \(G\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite