// Workers AI · dad joke modeWhat did list edge-coloring say? "I'm on the edge of a new hue.

Unsolved problem in mathematics

For every graph, is the list chromatic index equal to the chromatic index?

In graph theory, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color.

A graph $G$ is $k$ -edge-choosable if every instance of list edge-coloring that has $G$ as its underlying graph and that provides at least $k$ allowed colors for each edge of $G$ has a proper coloring. In other words, when the list for each edge has length $k$ , no matter which colors are put in each list, a color can be selected from each list so that $G$ is properly colored. The edge choosability, or list edge colorability, list edge chromatic number, or list chromatic index, $ch'(G)$ of graph $G$ is the least number $k$ such that $G$ is $k$ -edge-choosable. It is conjectured that it always equals the chromatic index.

Properties

Here $χ' (G)$ is the chromatic index of $G$ ; and $K n,n$ , the complete bipartite graph with equal partite sets.

Some properties of $ch'(G)$ :

$\operatorname {ch} '(G)<2\chi '(G).$
$\operatorname {ch} '(K_{n,n})=n.$ This is the Dinitz theorem, proven by Galvin (1995).
$\operatorname {ch} '(G)<(1+o(1))\chi '(G),$ i.e. the list chromatic index and the chromatic index agree asymptotically (Kahn 2000).
For bipartite graphs, $ch'(G)=\chi '(G)$ .^[1] For every simple bipartite graph, $ch'(G)=\Delta$ .^[2]

List coloring conjecture

The most famous open problem about list edge-coloring is probably the list coloring conjecture.

$\operatorname {ch} '(G)=\chi '(G).$

This conjecture has a fuzzy origin; Jensen & Toft (1995) overview its history. The Dinitz conjecture, proven by Galvin (1995), is the special case of the list coloring conjecture for the complete bipartite graphs $K n,n$ .

References

↑ Galvin, Fred (June 28, 1994). "The List Chromatic Index of a Bipartite Multigraph" (PDF). Journal of Combinatorial Theory Series B. 63: 153–158.
↑ Bondy, J. A.; Murty, U. S. R. (2008). Graph theory. New York: Springer. pp. 466–469. ISBN 978-1-84628-969-9.

Galvin, Fred (1995), "The list chromatic index of a bipartite multigraph", Journal of Combinatorial Theory, Series B, 63: 153–158, doi:10.1006/jctb.1995.1011.
Jensen, Tommy R.; Toft, Bjarne (1995), "12.20 List-Edge-Chromatic Numbers", Graph Coloring Problems, New York: Wiley-Interscience, pp. 201–202, ISBN 0-471-02865-7.
Kahn, Jeff (2000), "Asymptotics of the list chromatic index for multigraphs", Random Structures & Algorithms, 17 (2): 117–156, doi:10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9

[1] Galvin, Fred (June 28, 1994). "The List Chromatic Index of a Bipartite Multigraph" (PDF). Journal of Combinatorial Theory Series B. 63: 153–158.

[BondyMurty-2] Bondy, J. A.; Murty, U. S. R. (2008). Graph theory. New York: Springer. pp. 466–469. ISBN 978-1-84628-969-9.

[1]

[2]

This page was redesigned at the edge.

A page that knows where it met you.

// Workers AI · dad joke modeWhat did list edge-coloring say? "I'm on the edge of a new hue.

Properties

List coloring conjecture

References