Edge list coloring conjecture

Importance: High ✭✭✭
Author(s):
Subject: Graph Theory
» Coloring
» » Edge coloring
Keywords:
Recomm. for undergrads: no
Posted by: tchow
on: September 25th, 2008

\begin{conjecture} Let $G$ be a loopless multigraph. Then the edge chromatic number of $G$ equals the list edge chromatic number of $G$. \end{conjecture}

The list edge chromatic number of $G$ is also known as the \emph{list chromatic index}, the \emph{edge choosability}, or the \emph{edge choice number} of $G$. It is the list chromatic number of the line graph of $G$. Similarly, the edge chromatic number of $G$ is also known as the \emph{edge chromatic index}, and it is the chromatic number of the line graph of $G$. The chromatic number of a graph is always less than or equal to the list chromatic number; the two quantities differ in general, but the conjecture says that they coincide for line graphs. Sometime the conjecture is simply referred to as the \emph{list coloring conjecture}, although this is perhaps poor terminology since there exist other conjectures about list coloring.

Perhaps the most famous partial result is Galvin's theorem [G] that the conjecture holds for bipartite multigraphs. Galvin's result settled the well-known \emph{Dinitz conjecture} in the affirmative.

The conjecture has been attributed to many different people. See [JT, Problem 12.20] for a history of the problem up to 1995.

Bibliography

[G] Fred Galvin, The list chromatic index of a bipartite multigraph. J. Combin. Theory Ser. B 63 (1995), 153–158.

[JT] Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems. New York: Wiley-Interscience, 1995.


* indicates original appearance(s) of problem.