Edge list coloring conjecture

Edge list coloring conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected loopless multigraph. Parallel edges are distinguished and share both endpoints. A proper edge colouring assigns a colour to each edge so that different edges sharing an endpoint receive different colours. The edge chromatic number, or chromatic index, $\chi'(G)$ is the minimum number of colours in such a colouring.

An edge-list assignment specifies a finite set $L(e)$ of allowed colours for every $e\in E$. An $L$-edge-colouring is a proper edge colouring $c$ with $c(e)\in L(e)$ for all $e$. Define $\chi'_\ell(G)$ to be the least nonnegative integer $q$ such that every assignment with $|L(e)|\geq q$ for all edges has an $L$-edge-colouring. For an edgeless graph both parameters are zero.

The conjecture is \[ \chi'_\ell(G)=\chi'(G) \qquad\text{for every finite loopless multigraph }G. \] The lists are arbitrary: they need not be equal, and their union can be much larger than $\chi'(G)$. Assigning the same $q$-element list to every edge immediately gives $\chi'_\ell(G)\geq\chi'(G)$; the opposite inequality is the requested result.

Equivalently, ordinary chromatic number and list chromatic number should coincide on line graphs of loopless multigraphs, whose vertices represent edges and whose adjacency records common endpoints. The conjecture does not request a bound solely in terms of maximum degree.

Short English statement

Are as many colours per arbitrary edge list as the ordinary chromatic index always sufficient for proper edge colouring?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 1 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope.

Literature and a tractable class.

Galvin [R1] proves the entire bipartite multigraph case, a substantially stronger theorem than the elementary forest argument developed here. The distinction between lists on edges and lists on vertices is essential: this conjecture concerns list colouring of line graphs. We prove equality for every simple pseudoforest, meaning every connected component has at most one cycle, and identify why the same deletion argument stops in a general graph.

Leaf extension.

Fix an integer $d\ge\Delta(G)$ and lists of size at least $d$ on the edges. Delete a leaf edge $uv$, with $u$ a leaf. After colouring the remaining graph, at most $d-1$ already coloured edges meet $v$, and no other coloured edge meets $u$. At least one member of $L(uv)$ therefore remains available. Repeated deletion proves that every forest is edge-$\Delta$-choosable. The lower bound $\chi'(G)\ge\Delta$ follows from the mutually adjacent edges at a maximum-degree vertex, so equality follows for nonempty forests. An edgeless graph has both parameters zero under the stated convention.

The cycle kernel.

The line graph of a simple cycle of length $m$ is again $C_m$. Every cycle is list-colourable from lists of size three: colour a path obtained by deleting one vertex, then colour that vertex avoiding its two neighbours. An even cycle is list-colourable from lists of size two. To see the latter, first reduce larger lists to two elements each. If all lists are the same, alternate those two colours. Otherwise some consecutive vertices have different lists. Number them $v_1,v_m$ and choose $c(v_1)\in L(v_1)\setminus L(v_m)$. Colour $v_2,\ldots,v_m$ in order, avoiding the immediately preceding colour. The closing edge is safe because the first colour is absent from the last list. This second argument works on either parity of cycle when the lists differ. Identical two-element lists on an odd cycle give the necessary obstruction to two colours.

A complete restricted theorem.

In a pseudoforest, delete leaf edges until each remaining nontrivial component is a cycle. If $\Delta\ge3$, colour those cycles from the original $\Delta$-element lists using the preceding three-list argument, then restore all deleted edges in reverse order. The leaf extension never runs out of colours. This proves $\chi'_\ell=\chi'=\Delta$ in that case. When $\Delta\le2$, components are paths, isolated vertices and cycles. The forest cases already give equality, including maximum degree zero or one. If a cycle occurs, use two colours unless an odd cycle occurs, in which case three are both necessary and sufficient. These arguments also handle a disconnected mixture of components: their palettes may be reused because no edges join different components. No assumption of a common list palette was made.

A universal bound and the obstruction to improving it.

For a loopless multigraph of maximum degree $\Delta\ge1$, an edge $uv$ with multiplicity $\mu(uv)$ has $d(u)+d(v)-\mu(uv)-1\le2\Delta-2$ neighbours in its line graph. Thus ordinary greedy list colouring gives $\chi'_\ell(G)\le2\Delta-1$. Reducing that bound to $\chi'(G)$ needs more than deleting an arbitrary edge: both endpoints can already forbid colours, and there need not be a leaf or an isolated cycle kernel. Moreover, exchanging two colours on a Kempe chain can move an edge to a colour absent from its own list. A valid ordinary edge-colouring recolouring therefore does not automatically give a valid list recolouring.

Verification and final status.

The arguments cover the empty graph, odd and even cycles, and arbitrary list overlaps. The proof of the two-list cycle step is constructive and does not infer universal choosability from finite palette tests. UNRESOLVED. Equality is established here for simple pseudoforests; the general loopless multigraph statement is not proved. The first missing step is an extension or recolouring principle that survives a nontrivial core and respects every individual edge list.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3202 (OPG-2110), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Edge list coloring conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/edge_list_coloring_conjecture.
• R1 Fred Galvin, The List Chromatic Index of a Bipartite Multigraph, Journal of Combinatorial Theory, Series B 63 $1995$, 153--158. Primary abstract checked 1 October 2026. https://doi.org/10.1006/jctb.1995.1011.