Problem 12.20: List-Edge-Chromatic Numbers

J. Kahn has kindly pointed out that the most important new result (Theorem 5.11) of the survey paper on hypergraphs, listed in the reference section to Chapter 9 of "Graph Coloring Problems" as Kahn [1994b], gives as one special case (Theorem 5.10 of the paper) that the list-edge-chromatic number of a simple graph with maximum degree D is asymptotically D + o(D).

In the text of Problem 12.20 we credit this result to R. Häggkvist and J.C.M. Janssen. We note in this connection that we have erroneously given the asymptotic bound as "D + o(1)", which, as it was again kindly pointed out by J. Kahn, should have been "D + o(D)".

June 15, 1995 Tommy R. Jensen

The case of Problem 12.20 when G is a series-parallel graph has been solved by M. Juvan, B. Mohar and R. Thomas, "List-edge colorings of series-parallel graphs", Electronic Journal of Combinatorics 6(1), 1999.

December 8, 2000 Tommy R. Jensen

Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified December 8, 2000 Tommy R. Jensen