MathDB

Vizing’s list edge-colouring conjecture

For every loopless multigraph GG, the list edge-chromatic number equals the edge-chromatic number: ch⁡′(G)=χ′(G)\operatorname{ch}'(G)=\chi'(G). Equivalently, if each edge of GG is assigned a list of at least χ′(G)\chi'(G) colors, then GG has a proper edge coloring choosing for each edge a color from its list.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Vizing's Δ+1\Delta+1 list edge-coloring formulation

    For every loopless multigraph GG with maximum degree Δ\Delta, ch⁡′(G)≤Δ+1\operatorname{ch}'(G)\leq\Delta+1.

    source: Signed list edge coloring in graphs of bounded treewidth

References

Primary source

arXiv

Additional references

graph-theorylist-colouring
Posted

Progress summary

Refreshed
Claimed progress

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 ch⁡′(G)=χ′(G)\operatorname{ch}'(G)=\chi'(G). It remains unresolved for arbitrary graphs.

Known results

  • Bipartite multigraphs satisfy the conjecture (Galvin, 1995), including the Dinitz conjecture.
  • For general graphs, ch⁡′(G)<(1+o(1))χ′(G)\operatorname{ch}'(G)<(1+o(1))\chi'(G) asymptotically (Kahn, 2000).

August 2026 signed extension

Zhang, Li, Lu, You, Miao, Zhengke, Wang, and Yintao prove the signed analogue χl′(G,σ)≤Δ+1\chi_l'(G,\sigma)\le \Delta+1 when the underlying graph has treewidth 33, or treewidth 44 with Δ≥10\Delta\ge 10. This extends Lang’s ordinary treewidth-33 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.

Sources

Solutions 0

No solutions have been posted yet.