Vizing’s list edge-colouring conjecture
For every loopless multigraph , the list edge-chromatic number equals the edge-chromatic number: . Equivalently, if each edge of is assigned a list of at least colors, then has a proper edge coloring choosing for each edge a color from its list.
Equivalent formulations
For every loopless multigraph with maximum degree , .
source: Signed list edge coloring in graphs of bounded treewidth
References
- Signed list edge coloring in graphs of bounded treewidth — arXiv — Zhang, Li, Lu, You, Miao, Zhengke, Wang, Yintao
Source: arXiv
Progress summary
A new result proves the bound for several restricted signed graph classes, but the original problem for all graphs remains open.
The conjecture asks whether every loopless multigraph has list edge-chromatic number equal to its edge-chromatic number, equivalently whether . It remains unresolved for arbitrary graphs.
Known results
- Bipartite multigraphs satisfy the conjecture (Galvin, 1995), including the Dinitz conjecture.
- For general graphs, asymptotically (Kahn, 2000).
August 2026 signed extension
Zhang, Li, Lu, You, Miao, Zhengke, Wang, and Yintao prove the signed analogue when the underlying graph has treewidth , or treewidth with . This extends Lang’s ordinary treewidth- result but does not settle the original conjecture.
Current status (as of August 2026): The conjecture is settled for bipartite multigraphs and several further restricted classes, including the stated signed bounded-treewidth cases, but remains open for arbitrary graphs.
Solutions 0
No solutions have been posted yet.