# 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