Problem 17.2: List-Coloring the Union of Graphs


The more general conjecture of Erdős, Rubin and Taylor mentioned in the remarks to Problem 17.2 has been studied by Tuza and Voigt in two papers:

Zs. Tuza and M. Voigt, Every 2-choosable graph is (2m,m)-choosable, J. Graph Theory 22 (1996), 245-252.

Zs. Tuza and M. Voigt, On a conjecture of Erdős, Rubin and Taylor, Tatra Mountains Math. Publ. 9 (1996), 69-82.

From the Abstract of the last mentioned paper:

In 1979, Erdős, Rubin and Taylor raised the conjecture that every (a,b)-choosable graph G is also (am,bm)-choosable for all m>1. We investigate the case b=1, presenting some classes of (a,1)-choosable graphs for which (am,m)-choosability can be proved for all m.

Recently a long, interesting and very informative survey has appeared:

Zs. Tuza, Graph Colorings with Local Constraints - A Survey, to appear in Discussiones Mathematicae Graph Theory 17 (1997), Manuscript, 67 pages.

August 14, 1997. Bjarne Toft


Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified August 14, 1997. Bjarne Toft