Is every line graph $\{1\star(\chi'(G)-3),\,3\}$-choosable?

The List Colouring Conjecture (LCC) predicts that the line graph $L(G)$ of every graph $G$ is $\chi'(G)$-choosable, where $\chi'(G)$ is the chromatic index; it is open in general, even for complete graphs of even order. The framework of $\lambda$-choosability refines the scale between $k$-colourability and $k$-choosability by constraining how list entries are distributed across a partitioned palette: for a multiset $\lambda=\{k_1,\dots,k_q\}$, a $\lambda$-list assignment partitions the colour set into classes $C_1,\dots,C_q$ with each vertex's list containing at least $k_i$ colours from $C_i$. In this framework it is known that $L(G)$ is $\lambda$-choosable whenever $\lambda$ partitions $\chi'(G)$ into parts of size at most 2, and Zhu and Zhu posed the natural next question: is $L(G)$ always $\{1\star(\chi'(G)-3),3\}$-choosable, with one palette class of size 3 and $\chi'(G)-3$ singleton classes? This question is recorded as open [1], and no resolution is known in the literature to date. When $\chi'(G)=3$ the multiset degenerates to $\{3\}$, so the question specialises exactly to the LCC for graphs of chromatic index 3.

Background

List colouring extends ordinary graph colouring by assigning each vertex $v$ its own set $L(v)$ of permissible colours and requiring a proper colouring with $f(v)\in L(v)$ for every $v$. A graph is $k$-choosable if such a colouring exists for every assignment of lists of size at least $k$, and the choice number $\operatorname{ch}(G)$ is the least such $k$; always $\operatorname{ch}(G)\ge\chi(G)$. A graph with $\operatorname{ch}(G)=\chi(G)$ is called chromatic-choosable. The most famous conjecture in this area is the List Colouring Conjecture (LCC), stated in several equivalent forms in the 1970s (see the 2026 dynamic survey of Vasudevan, Somasundaram and Narayanan): line graphs are chromatic-choosable. The line graph $L(G)$ has the edges of $G$ as vertices, two of them adjacent when the corresponding edges share an endpoint; edge colouring of $G$ is vertex colouring of $L(G)$, so the conjecture says $\operatorname{ch}(L(G))=\chi(L(G))=\chi'(G)$, where the chromatic index $\chi'(G)$ is the minimum number of colours in a proper edge colouring of $G$. Equivalently, every edge-$k$-colourable graph is edge-$k$-choosable. Galvin confirmed the conjecture for bipartite multigraphs, and various further classes are verified (snarks, i.e. bridgeless cubic graphs that are not 3-edge-colourable; odd complete graphs; series-parallel graphs; and others), but the conjecture is open in general — for instance it is unknown for complete graphs of even order, as Xuding Zhu's 2020 paper records.

The framework of $\lambda$-choosability, introduced by Xuding Zhu in 2020, interpolates between colourability and choosability. For a multiset $\lambda=\{k_1,\dots,k_q\}$ of positive integers with $k_\lambda=\sum_i k_i$ (writing $1\star m$ for $m$ copies of the integer 1), a $\lambda$-list assignment of $G$ is a list assignment $L$ whose colour set $\bigcup_v L(v)$ can be partitioned into disjoint classes $C_1\cup\dots\cup C_q$ such that $|L(v)\cap C_i|\ge k_i$ for every vertex $v$ and every $i$; $G$ is $\lambda$-choosable if it is $L$-colourable for every $\lambda$-list assignment $L$. If $\lambda=\{k\}$ this is ordinary $k$-choosability, and if $\lambda=\{1\star k\}$ it is equivalent to $k$-colourability; every $\lambda$-choosable graph is $k_\lambda$-colourable, and every $k_\lambda$-choosable graph is $\lambda$-choosable, since a $\lambda$-list assignment is a $k_\lambda$-list assignment with extra structure. The partitions of $k$ thus form a strict hierarchy of colourability strengths between $k$-colourability and $k$-choosability.

For line graphs the frontier of this hierarchy is sharp. Zhu proved that if $\lambda$ partitions $\chi'(G)$ and every part of $\lambda$ has size at most 2, then $L(G)$ is $\lambda$-choosable: the proof decomposes a proper $\chi'(G)$-edge-colouring into groups of at most two colour classes, each inducing matchings, paths, and even cycles — structures whose line graphs are choosable from the corresponding palette class by classical results — and colours each group from its own class, the classes being disjoint. He also proved that for even $n$, the complete graph $K_n$ is edge-$\lambda$-choosable for every partition of $n-1=\chi'(K_n)$ into parts of size at most 3. A palette class of size 3, however, groups three colour classes of the decomposition into a subgraph of maximum degree 3 that is 3-edge-colourable, and whether such subgraphs are edge-3-choosable is exactly the LCC in the chromatic-index-3 case — the obstacle the open question confronts. The question was recorded by Jialu Zhu and Xuding Zhu in their work on minimum non-chromatic-$\lambda$-choosable graphs, the $\lambda$-analogue of the study of $\varphi(k)$, the minimum order of a $k$-chromatic non-$k$-choosable graph (Ohba's conjecture, confirmed by Noel, Reed and Wu, asserts $\varphi(k)\ge 2k+2$); having determined $\varphi(\lambda)$ for all $\lambda$, they explicitly recorded the line-graph question as a natural unresolved problem.

Problem Statement

Let $G$ be a graph of chromatic index $\chi'(G)\ge 3$ and let $L(G)$ be its line graph. For the multiset $\lambda=\{1\star(\chi'(G)-3),\,3\}$, that is, $\chi'(G)-3$ copies of the integer 1 together with one integer 3 (so $k_\lambda=\chi'(G)$ and $\lambda$ has $\chi'(G)-2$ parts), is $L(G)$ always $\lambda$-choosable?

Explicitly: whenever each edge $e$ of $G$ receives a list $L(e)$ of colours and the colour set $\bigcup_{e\in E(G)}L(e)$ can be partitioned into disjoint classes $C_1\cup\dots\cup C_{\chi'(G)-2}$ such that every edge's list contains at least one colour from each of $C_1,\dots,C_{\chi'(G)-3}$ and at least three colours from $C_{\chi'(G)-2}$, must $G$ admit a proper edge colouring in which each edge $e$ receives a colour from $L(e)$?

This is the question posed by Zhu and Zhu. When $\chi'(G)=3$ the multiset is $\{3\}$ and the question specialises to: is every 3-edge-colourable graph edge-3-choosable — the List Colouring Conjecture for the class of graphs with chromatic index 3. For $\chi'(G)\ge 4$ the statement is strictly weaker than the LCC for $G$, sitting between $\chi'(G)$-edge-colourability (which always holds) and $\chi'(G)$-choosability of $L(G)$ (the LCC).

References

1. Jialu Zhu and Xuding Zhu, Minimum non-chromatic-$\lambda$-choosable graphs, arXiv:2208.02050 (2022); published as Journal of Graph Theory 110 (2025) 283-289, DOI 10.1002/jgt.23267, https://arxiv.org/abs/2208.02050 (an extended abstract with the same title and content appeared at EUROCOMB'23, DOI 10.5817/cz.muni.eurocomb23-115)
2. Xuding Zhu, A refinement of choosability of graphs, Journal of Combinatorial Theory, Series B 141 (2020) 143-164, DOI 10.1016/j.jctb.2019.07.006, arXiv:1811.08587, https://arxiv.org/abs/1811.08587
3. Jialu Zhu and Xuding Zhu, Chromatic $\lambda$-choosable and $\lambda$-paintable graphs, Journal of Graph Theory 98 (2021) 642-652, DOI 10.1002/jgt.22718, arXiv:1910.12509, https://arxiv.org/abs/1910.12509
4. Yangyan Gu and Xuding Zhu, Girth and $\lambda$-choosability of graphs, Journal of Graph Theory 103 (2023) 493-501, DOI 10.1002/jgt.22931, arXiv:2109.00776, https://arxiv.org/abs/2109.00776
5. Yangyan Gu, Yiting Jiang, David R. Wood and Xuding Zhu, Refined list version of Hadwiger's conjecture, SIAM Journal on Discrete Mathematics 37 (2023) 1738-1750, DOI 10.1137/22M1522413, arXiv:2209.07013, https://arxiv.org/abs/2209.07013
6. Nandana K. Vasudevan, K. Somasundaram and N. Narayanan, List-Coloring and Chromatic-Choosability — A Dynamic Survey, arXiv:2606.31702 (2026), https://arxiv.org/abs/2606.31702
7. Chunqiu Fang and Rongxing Xu, Codegree Thresholds for $\lambda$-Choosability of Graphs, arXiv:2608.16740 (2026), https://arxiv.org/abs/2608.16740
8. Kengo Enami and Hikaru Yokoi, On partial order of $\lambda$-choosability for planar graphs, Discrete Mathematics 349 (2026), article 115115, DOI 10.1016/j.disc.2026.115115, https://doi.org/10.1016/j.disc.2026.115115
9. Evan Leonard, Strictly $k$-colorable graphs, Discrete Mathematics 349 (2026), article 114980, DOI 10.1016/j.disc.2026.114980, arXiv:2307.05461, https://arxiv.org/abs/2307.05461
10. Kyoji Ohba, On chromatic-choosable graphs, Journal of Graph Theory 40 (2002) 130-135, DOI 10.1002/jgt.10033, https://doi.org/10.1002/jgt.10033
11. Jonathan A. Noel, Bruce A. Reed and Hehui Wu, A proof of a conjecture of Ohba, Journal of Graph Theory 79 (2015) 86-102, DOI 10.1002/jgt.21819, https://doi.org/10.1002/jgt.21819
12. Fred Galvin, The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory, Series B 63 (1995) 153-158, DOI 10.1006/jctb.1995.1011, https://doi.org/10.1006/jctb.1995.1011