List edge-coloring conjecture

List edge-coloring conjecture

Definitions and mathematical statement

Let $G$ be a finite loopless multigraph, allowing parallel edges. A proper edge coloring assigns different colors to every pair of edges sharing a vertex. The ordinary chromatic index $\chi'(G)$ is the smallest number of colors permitting one. Its list chromatic index $\chi'_\ell(G)$ is the least $k$ such that, for every assignment of a list $L(e)$ of $k$ permitted colors to each edge, a proper edge coloring $c$ exists with $c(e)\in L(e)$.

The conjecture is \[ \chi'_\ell(G)=\chi'(G)\qquad\text{for every finite loopless multigraph }G. \] Different edges may have entirely different lists; taking all lists equal gives only the ordinary coloring problem. The statement concerns edge lists, not vertex-list coloring, and the absence of loops is essential to the standard proper-coloring definition.

Formulation and concept references: [S1].

Short English statement

Does assigning each edge its own list of colors ever require larger lists than the number of colors needed for ordinary edge coloring?

Research attempt

Quantifiers and source audit (27 September 2026).

Fix a finite loopless multigraph $G$. The target is that every assignment of finite sets $L(e)$ with $|L(e)|\geq k=\chi'(G)$ can be colored. The color names have no order or numerical meaning. It is harmless to truncate larger lists to size $k$, but it is not harmless to replace them by one common palette. Parallel edges are distinct vertices of the line graph and must receive distinct colors. For an edgeless graph both indices are zero.

The publisher page in [S1] was not directly retrievable in this session; the author's version, arXiv:2307.12094v3, dated 15 January 2025, was retrieved [E1]. Its introduction states the unrestricted conjecture and distinguishes its own hypotheses on colors common to the edges at a vertex. Those common-intersection hypotheses do not follow from large individual lists. Galvin's original publication states equality for bipartite multigraphs [E2]. Borodin--Kostochka--Woodall prove the stronger bipartite condition $|L(uv)|\geq\max\{d(u),d(v)\}$ [E3]. The argument below reconstructs the uniform-$k$ bipartite theorem, not that stronger local result and not a new advance beyond it.

The principal attack is to find an orientation of the line graph with small outdegrees and a kernel in every induced subdigraph. A successful orientation converts an ordinary $k$-edge-coloring into a proof for all $k$-lists. The bipartite construction can be proved completely by a stable-matching algorithm. I then try to extend that construction by assigning opposite preference orders to vertices of an arbitrary graph; a six-edge example gives an explicit obstruction to this extension.

Baseline bound and the shape of a minimal bad assignment.

The line graph $H$ has one vertex for each edge of $G$, with adjacency when the two edges have a common endpoint. For an edge $e=uv$, let $\mu(u,v)$ be the number of parallel edges between its endpoints. Then \begin{equation}\label{wsref-0-72-61-34-39-36-3a-6c-69-6e-65-2d-64-65-67-72-65-65} d_H(e)=d_G(u)+d_G(v)-\mu(u,v)-1. \end{equation} Indeed there are $d_G(u)-1$ other edges at $u$ and $d_G(v)-1$ at $v$, with exactly $\mu(u,v)-1$ counted twice. Greedy coloring in any order therefore works whenever \[ |L(uv)|\geq d_G(u)+d_G(v)-\mu(u,v) \quad\text{for every edge }uv. \] At the moment an edge is colored, at most its number of neighbors can exclude colors. In particular, for $G$ nonempty, \begin{equation}\label{wsref-0-72-61-34-39-36-3a-67-72-65-65-64-79} \chi'_\ell(G)\leq2\Delta(G)-1\leq2\chi'(G)-1. \end{equation} This is a fully checked bound, but its fixed factor cannot be mistaken for the desired equality.

Suppose a particular assignment of $k$-lists is bad, and choose a nonempty edge subset $F$ minimal under inclusion on which the restricted lists are still uncolorable. For every $uv\in F$, \begin{equation}\label{wsref-0-72-61-34-39-36-3a-63-72-69-74-69-63-61-6c} d_F(u)+d_F(v)-\mu_F(u,v)-1\geq k. \end{equation} Otherwise color $F\setminus\{uv\}$ by minimality and extend to $uv$, which has fewer than $k$ colored neighbors. Thus a counterexample cannot be detected by merely repeatedly removing an edge of small line degree. For example, a cubic simple graph has line degree four at every edge, although some such graphs have ordinary chromatic index three. The target requires using the arrangement of conflicting neighbors, not only how many there are.

A general certificate for list colorability.

A directed graph here can have both opposite arcs on the same pair of vertices, but no loops. Its underlying undirected graph contains an edge exactly when at least one of the arcs is present. A kernel is an independent set $K$ such that every vertex outside $K$ has an outgoing arc to a member of $K$. The digraph is kernel-perfect if every induced subdigraph has a kernel. The empty digraph has the empty kernel; a nonempty digraph cannot have the empty set as a kernel.

Lemma 496.1 (kernel coloring lemma). Let $D$ be a kernel-perfect orientation, allowing opposite arcs, of a finite graph $H$. If $|L(v)|\geq d_D^+(v)+1$ for every vertex, then $H$ has an $L$-coloring.

Proof. Induct on the number of vertices, the empty case being immediate. Choose a color $a$ occurring in a list, and let $S=\{v:a\in L(v)\}$. Take a kernel $K$ of $D[S]$ and give every member of $K$ color $a$. This is a proper assignment because $K$ is independent. Delete $K$ and remove $a$ from every remaining list in $S$.

For $v\in S\setminus K$, the kernel property supplies an outgoing neighbor in $K$. Its outdegree drops by at least one, compensating for the removal of one list color. For $v\notin S$, the list is unchanged and the outdegree cannot increase. The residual lists therefore still have size at least one more than the residual outdegrees. Every induced subdigraph of $D-K$ is an induced subdigraph of $D$, so kernel-perfection is inherited. Induction colors the remaining vertices. No remaining vertex uses color $a$, which prevents a conflict with $K$.$\square$

This gives a precise sufficient goal for the conjecture: for every $k$-edge-colorable multigraph, construct a kernel-perfect orientation of its line graph with maximum outdegree at most $k-1$. It is only a sufficient goal; failure of a proposed orientation does not imply that some lists are uncolorable.

The bipartite construction, including parallel edges.

Let $G$ be bipartite with parts $X,Y$, and fix any proper ordinary edge-coloring $\varphi:E(G)\to\{1,\ldots,k\}$. Its existence is the only fact about the ordinary chromatic index needed here. Direct a line-graph adjacency from $e$ to $f$ if they meet at $x\in X$ and $\varphi(e)>\varphi(f)$, or if they meet at $y\in Y$ and $\varphi(e)<\varphi(f)$. Parallel edges meet at both ends, and receive opposite arcs. This is deliberate: suppressing one of those arcs could destroy the kernel argument.

If $\varphi(e)=i$, at its $X$ endpoint there are at most $i-1$ edges with smaller colors; at its $Y$ endpoint there are at most $k-i$ with larger colors. A proper edge-coloring has at most one edge of each color at a vertex. Hence \begin{equation}\label{wsref-0-72-61-34-39-36-3a-6f-75-74-64-65-67-72-65-65} d_D^+(e)\leq(i-1)+(k-i)=k-1. \end{equation} The two sets counted here are disjoint even for parallel edges: no color is both less and greater than $i$. Incoming arcs or the presence of an opposite arc do not alter this outdegree estimate.

Lemma 496.2 (the induced-subgraph kernel). For every subset $F\subseteq E(G)$, the induced digraph $D[F]$ has a kernel.

Proof. At each vertex of $X$ prefer incident edges in $F$ with smaller $\varphi$-values; at each vertex of $Y$ prefer larger values. These are strict preferences because incident edges have distinct colors. Run the following proposal algorithm. An unmatched vertex $x\in X$ with an unproposed incident edge proposes its most preferred remaining edge to its other endpoint $y$. The vertex $y$ keeps the edge it prefers between the proposal and any edge it is already keeping, rejecting the other. A rejected $X$ vertex becomes unmatched. The kept edges always form a matching, and every proposal is a previously unproposed edge, so the process terminates after at most $|F|$ proposals.

Let $M$ be the final matching. For an edge $e=xy\notin M$, if $x$ never proposed $e$, then it finishes matched to a preferred edge: otherwise it would still have an allowable proposal at termination. If $x$ did propose $e$, vertex $y$ rejected it either immediately or later; the edge that $y$ keeps can only improve in its strict preference order, so $y$ finishes matched to an edge it prefers to $e$. In either case there is an $f\in M$ with an arc $e\to f$. Since a matching is an independent set of the line graph, $M$ is a kernel of $D[F]$.

The algorithm remains valid for parallel edges: proposals are distinct edges, and a matched $X$ vertex does not make a new proposal. The proof uses the individual preference comparisons, so it does not require a simple underlying graph.$\square$

Combining the two lemmas with (ra496:outdegree) proves that every $k$-edge-colorable bipartite multigraph is $k$-edge-choosable. Set $k=\chi'(G)$ and use constant lists to obtain the opposite inequality $\chi'_\ell(G)\geq\chi'(G)$. This proves equality in the bipartite subcase. The proof is the classical orientation/stable-matching mechanism behind Galvin's theorem, reconstructed here to identify exactly which features might extend; see [E2,E3]. It does not rely on an unproved formula for $\chi'(G)$.

Attempt to extend the certificate: an explicit obstruction.

The most direct extension assigns each vertex a sign. At a $+$ vertex, orient conflicts toward the edge with smaller ordinary color; at a $-$ vertex, orient them toward the larger color. Opposite signs on every edge give the bipartite construction. A general graph does not admit such a sign assignment, but perhaps some same-sign edges could be allowed while keeping the outdegree bound and kernel-perfection.

The graph $K_4$ defeats this particular proposal already for $k=3$. Label vertices $0,1,2,3$ and color its edges by \[ \varphi(01)=\varphi(23)=1,\qquad \varphi(02)=\varphi(13)=2,\qquad \varphi(03)=\varphi(12)=3. \] This is a proper three-edge-coloring, and degree three makes it optimal. For a color-one edge, two negative endpoints would produce outdegree four, so such endpoints are forbidden if $d^+\leq2$. For a color-three edge, two positive endpoints are likewise forbidden. The middle-color edges always have outdegree two, regardless of the signs.

If both endpoints of $01$ were positive, the color-three edges $03$ and $12$ would force $3$ and $2$ negative, contradicting the color-one edge $23$. Thus both color-one edges must have opposite signs. The same argument, with positive and negative interchanged, applies to the two color-three edges. These four edges form the cycle $0,1,2,3,0$, so the only sign assignments with maximum outdegree at most two are \[ (+,-,+,-)\quad\text{and}\quad(-,+,-,+). \] For the first assignment, the three vertices $01,12,02$ of the line graph form the directed cycle \[ 01\longrightarrow12\longrightarrow02\longrightarrow01. \] Indeed the preferences at $1,2,0$, respectively, give these directions. The other assignment reverses all three arcs. A directed three-cycle has no kernel: an independent set has at most one vertex, and one of the other vertices has no outgoing arc to that vertex. Therefore neither orientation is kernel-perfect.

Every proper three-edge-coloring of $K_4$ consists of its three perfect matchings, so relabeling vertices and colors reduces it to the displayed one. The obstruction rules out this whole sign-and-color recipe for $K_4$, not just a poor initial choice of ordinary coloring. It does not produce bad lists for $K_4$, and it does not rule out a more general orientation or a different list-coloring method.

This identifies the first real gap in the extension: bounded outdegree can survive while kernels fail in a tiny induced subgraph. Checking a kernel for the whole line graph would not suffice either, because the coloring induction needs kernels for the color-defined sets $S$ and for every subsequent induced subdigraph.

Two other directions, checked rather than assumed.

First, the degree-at-most-two case can be completed directly. A connected loopless multigraph of maximum degree two is a path, a cycle, or a single vertex; a pair of parallel edges is the two-edge cycle. A path is greedily edge-colorable from arbitrary two-lists. For an even cycle, view its edges as cyclically ordered list vertices. If all two-lists coincide, alternate the two colors. Otherwise, choose consecutive unequal lists $L_1,L_m$ and a color $a\in L_1\setminus L_m$. Give edge one color $a$, and color edges $2,\ldots,m$ in order. Each step avoids the previous color; at the last step, $a\notin L_m$, so closing the cycle adds no additional forbidden list color. A two-edge cycle is colored greedily. An odd cycle has ordinary index three, and arbitrary three-lists can be colored greedily since each line vertex has degree two. Thus equality holds for all multigraphs of maximum degree at most two. For a disconnected graph use its global $k$ and truncate lists as needed on each component; a single isolated edge needs only one color.

Second, transferring an ordinary alternating-path argument to lists requires a membership condition at every recolored edge. For example, on a triangle give its three edges lists \[ \{1,4,5\},\quad\{2,4,5\},\quad\{3,4,5\}. \] The ordinary coloring $1,2,3$ respects those lists, but interchanging colors one and two on their two-edge alternating path immediately violates both lists. Adding arbitrary extra colors to all three lists does not repair that proposed swap. This is not an uncolorable list assignment; it is a precise failure of treating an ordinary color swap as automatically list-legal. An extension based on fans must keep track of allowed recolorings, or establish a new invariant ensuring that every swap remains in the relevant lists.

Finite verification and boundary checks.

The accompanying standard-Python program constructs the orientation for $K_{3,3}$ using $\varphi(x_i y_j)=1+(i+j\bmod3)$, and for the multigraph obtained by doubling every edge of $K_{2,2}$ using colors $1+2(i+j\bmod2)+c$, where $c\in\{0,1\}$ labels the copies. For each induced edge subset it searches all independent subsets and tests the outgoing-absorption condition defining a kernel. The results were \[ \begin{array}{c|r|r|r} G&\text{induced subsets checked}&\max d^+& \text{subsets with no kernel}\\ \hline K_{3,3}&512&2&0\\ 2K_{2,2}&256&3&0 \end{array} \] The notation $2K_{2,2}$ means doubled edges, not a disjoint union. For $K_4$ the program tests all $16$ sign assignments. Exactly two satisfy $\max d^+\leq2$; each has eight induced subsets with no kernel, including the triangle proved above. These are exhaustive checks for the specified finite orientations, not an exhaustive test over arbitrary multigraphs or color palettes.

The proofs explicitly allow opposite arcs and parallel edges, preserve the "every list assignment" quantifier, and handle empty induced subgraphs. The ordinary coloring $\varphi$ supplies preferences only; its numerical colors are not assumed to occur in any of the lists. The proposal algorithm uses all edges of the tested subset as acceptable choices. No perfect matching assumption is made, and unmatched vertices with no unused incident edge cause no problem in its stability proof.

Outcome.

Outcome: UNRESOLVED. The notebook proves the elementary greedy bound and necessary critical-degree condition, reconstructs the complete bipartite theorem, and proves the maximum-degree-two subcase. Its attempted extension is falsified at the level of the orientation certificate by an explicit $K_4$ calculation. None of these known subcases is presented as a new solution to the conjecture.

The missing ingredient is a method that works for arbitrary nonbipartite multigraphs at lists of size exactly $\chi'(G)$. For the selected route, one would need a broader kernel-perfect orientation construction or a replacement for the kernel induction that tolerates the displayed directed-cycle obstructions. Other concrete next steps are to incorporate list membership into a fan-recoloring invariant and to use (ra496:critical) to constrain an actual smallest bad assignment. No such invariant or classification is established here, and no bad $\chi'(G)$-list assignment has been found.

Sources

• S1 Multigraph edge-coloring with local list sizes. https://www.sciencedirect.com/science/article/pii/S0012365X25000287. Formulation source.
• E1 A. Dhawan, Multigraph edge-coloring with local list sizes, arXiv:2307.12094v3, 15 January 2025, Introduction and Definition 1.2. https://arxiv.org/html/2307.12094v3. Author version of [S1]; consulted 27 September 2026.
• E2 F. Galvin, The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory, Series B 63 $1995$, 153--158. https://www.sciencedirect.com/science/article/pii/S0095895685710118. Original theorem; publisher abstract verified 27 September 2026.
• E3 O. V. Borodin, A. V. Kostochka, and D. R. Woodall, List edge and list total colourings of multigraphs, Journal of Combinatorial Theory, Series B 71 $1997$, 184--204, Introduction and Section 2, especially Theorem 3. https://kostochk.web.illinois.edu/docs/old/jctb97bw.pdf. Author-hosted published paper; consulted 27 September 2026.