Let G=(V,E) be a finite loopless graph (multiple edges permitted). Two edges are adjacent if they share an endpoint. A proper edge coloring of G with color set C is a map c colon E→ C such that c(e)≠ c(f) whenever e and f are adjacent. The chromatic index chi'(G) is the least integer k for which there is a proper edge coloring of G using a color set of size k. A list assignment for G is a map L assigning to each edge e∈ E a finite set L(e) of colors. A proper L-edge-coloring of G is a map c colon E→bigcup_e∈ EL(e) with c(e)∈ L(e) for every e∈ E and c(e)≠ c(f) for every pair of adjacent edges e,f. For an integer k≥ 1, the graph G is k-edge-choosable if every list assignment L with |L(e)|≥ k for all e∈ E admits a proper L-edge-coloring. The list chromatic index operatornamech'(G) is the least k such that G is k-edge-choosable. Then for every such graph G, operatornamech'(G)=chi'(G).

List edge coloring conjecture

41 years old · traced to 1985

Let $G=(V,E)$ be a finite loopless graph (multiple edges permitted). Two edges are adjacent if they share an endpoint.

A proper edge coloring of $G$ with color set $C$ is a map $c\colon E\to C$ such that $c(e)\neq c(f)$ whenever $e$ and $f$ are adjacent. The chromatic index $\chi'(G)$ is the least integer $k$ for which there is a proper edge coloring of $G$ using a color set of size $k$ .

A list assignment for $G$ is a map $L$ assigning to each edge $e\in E$ a finite set $L(e)$ of colors. A proper $L$ -edge-coloring of $G$ is a map $c\colon E\to\bigcup_{e\in E}L(e)$ with $c(e)\in L(e)$ for every $e\in E$ and $c(e)\neq c(f)$ for every pair of adjacent edges $e,f$ . For an integer $k\ge 1$ , the graph $G$ is $k$ -edge-choosable if every list assignment $L$ with $|L(e)|\ge k$ for all $e\in E$ admits a proper $L$ -edge-coloring. The list chromatic index $\operatorname{ch}'(G)$ is the least $k$ such that $G$ is $k$ -edge-choosable.

Then for every such graph $G$ ,

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

Equivalent formulations

Let $G$ be a finite graph, and let $\chi'(G)$ be its chromatic index. A list edge-coloring assigns to each edge a list of available colors, and $G$ is $\chi'(G)$ -edge-choosable if every assignment of lists of size $\chi'(G)$ admits a proper edge-coloring from those lists. List edge-coloring conjecture. Every graph is $\chi'(G)$ -edge-choosable.

This conjecture asks whether the list chromatic index always equals the ordinary chromatic index. It is presented as an open problem motivating the paper's study of edge-coloring series-parallel multigraphs.
source: Cristina G. Fernandes and Robin Thomas, “Edge-coloring series-parallel multigraphs”, arXiv:1107.5370 (2011).
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.
source: Wikipedia
Let $G$ be a graph. Write $\chi'(G)$ for its edge-chromatic number and $\chi'_{\ell}(G)$ for its list edge-chromatic number, the least integer $k$ such that every assignment of lists of at least $k$ colors to the edges permits a proper list edge coloring. List Coloring Conjecture. Every graph $G$ verifies
$\chi'(G)=\chi'_{\ell}(G).$
The conjecture is widely open; the source notes that it is known for planar graphs of maximum degree at least $12$ , while the general case remains unresolved.
source: Marthe Bonamy, “Planar graphs with maximum degree D at least 8 are (D+1)-edge-choosable”, arXiv:1303.4025 (2013).
Let $G$ be a graph. Its list chromatic index $\chi'_{\ell}(G)$ is the least integer $k$ such that every edge-list assignment $L$ with $|L(e)|\geq k$ admits an $L$ -edge-colouring, while $\chi'(G)$ is the chromatic index of $G$ .

List Edge Colouring Conjecture.
$\chi'_{\ell}(G)=\chi'(G).$
This conjecture asks whether uniform list edge-colourability requires no more colours than ordinary edge-colourability. It is a classic open problem in list edge-colouring.
source: Marthe Bonamy, Michelle Delcourt, Richard Lang and Luke Postle, “Edge-colouring graphs with local list sizes”, arXiv:2007.14944 (2023).
For a graph $G$ , let $\chi'(G)$ be its edge-chromatic number and let $ch'(G)$ be its list edge-chromatic number.

The list-edge-coloring equality conjecture. For any graph $G$ ,
$ch'(G)=\chi'(G).$
This asserts that list edge-coloring requires no more colors than ordinary edge-coloring. The supplied source does not state whether the conjecture has been resolved.
source: Jonathan Narboni, “Vizing's edge-recoloring conjecture holds”, arXiv:2302.12914 (2023).

References

Wikipedia, List edge-coloring, the article this problem comes from.

Source: Wikipedia

graph-theory unsolved-problem

Posted 2 months ago · edited 3 weeks ago

Progress summary

Refreshed 2 months ago

Open · progress reported

The conjecture remains open in general, but a new report claims it for two additional infinite families of complete graphs.

The conjecture asserts that every loopless multigraph has the same list edge-chromatic number as ordinary edge-chromatic number. Its history is commonly associated with Jensen and Toft (1995).

Known results

Galvin (1995): equality holds for every bipartite multigraph.
Kahn (2000): asymptotically, the list chromatic index is at most $(1+o(1))\chi'(G)$ for multigraphs.
Häggkvist and Jansson: equality holds for complete graphs of class $2$ .
For every odd prime $p$ , equality holds for $K_{p+1}$ , including its paintability index.

August 24, 2026: two new complete-graph families

On August 24, 2026, a report on The List Edge-Coloring Conjecture for Two New Infinite Families of Complete Graphs stated that the conjecture was proved for $K_{p-1}$ and $K_{2p}$ . This is a claimed advance, but the supplied evidence does not independently verify the proofs; the general conjecture remains open.

Current status (as of August 2026): The conjecture is open for general loopless multigraphs; several classes and asymptotic regimes are settled, while the reported results for $K_{p-1}$ and $K_{2p}$ remain unverified here.

Sources

No solutions have been posted yet.