Open problems on the λ-choosability of planar graph families from Zhu's refinement of choosability

Zhu (2020) introduced λ-choosability, a refinement of list colouring that interpolates between k-colourability and k-choosability: lists must draw prescribed numbers of colours from global colour groups. He proved that the resulting hierarchy of graph classes is ordered exactly by refinement of partitions, and that for planar graphs the Four Colour Theorem is tight on this scale, since Kemnitz and Voigt had constructed a planar graph that is not $\{1,1,2\}$-choosable. Zhu's Section 6 poses further open questions about the place of classical planar families on this scale: $\{1,2\}$-choosability of triangle-free planar graphs and of planar graphs without cycles of lengths 4,5,6 or 4,5,6,7; $\{1,1,2\}$-, $\{1,3\}$- or $\{2,2\}$-choosability of planar graphs with no odd wheel; $\{2,2\}$-choosability of 3-chromatic planar graphs; existence of an edge-colouring threshold k(s) for partition-refined list edge colouring; and separation of pairwise incomparable partitions by a single graph.

Background

A proper colouring of a graph assigns distinct colours to adjacent vertices. In list colouring, each vertex $v$ receives a set (list) $L(v)$ of permissible colours, and one asks for a proper colouring with $f(v)\in L(v)$ for every vertex; a graph is $k$-choosable if such a colouring exists for every assignment of lists of size $k$. List colouring is strictly harder than ordinary colouring: by the Four Colour Theorem every planar graph is 4-colourable, Thomassen proved that every planar graph is 5-choosable, and Voigt constructed planar graphs that are not 4-choosable; Mirzakhani constructed a planar graph with chromatic number exactly 3 that is not 4-choosable. Among triangle-free planar graphs, Grötzsch's theorem gives 3-colourability, Voigt produced a triangle-free planar graph that is not 3-choosable, and every triangle-free planar graph is 4-choosable.

Zhu (2020) introduced a scale of notions between these extremes. A partition of an integer $k$ is a multiset $\lambda=\{k_1,\dots,k_q\}$ of positive integers with $k_1+\dots+k_q=k$. A $\lambda$-assignment is a $k$-assignment $L$ whose colour set $\bigcup_v L(v)$ splits into $q$ colour groups $C_1,\dots,C_q$ such that $|L(v)\cap C_i|=k_i$ for every vertex $v$ and every $i$; $G$ is $\lambda$-choosable if it is colourable from every $\lambda$-assignment. Thus $\{k\}$-choosability is ordinary $k$-choosability and $\{1,1,\dots,1\}$-choosability is $k$-colourability, and the partitions in between measure how much global structure the lists must have. On partitions of possibly different integers Zhu defines the order $\lambda\le\lambda'$ to mean that $\lambda'$ is a refinement of a partition obtained from $\lambda$ by increasing some parts, where one partition refines another if it is obtained by splitting parts and increasing a part enlarges the total; he proved that every $\lambda$-choosable graph is $\lambda'$-choosable if and only if $\lambda\le\lambda'$. Restricted to partitions of a fixed integer $k$ this order is exactly refinement, so the lattice of partitions of $k$ is exactly the hierarchy of notions, refinements being weaker requirements. For $k=4$: 4-choosability implies both $\{1,3\}$- and $\{2,2\}$-choosability, each of these implies $\{1,1,2\}$-choosability, which implies 4-colourability, while $\{1,3\}$ and $\{2,2\}$ are incomparable.

For planar graphs this scale is tight at the top: Kemnitz and Voigt constructed a planar graph with a 4-assignment in which all lists share two common colours and which is not colourable from these lists; such an assignment is a $\{1,1,2\}$-assignment (take the two common colours as singleton groups), so planar graphs that are not $\{1,1,2\}$-choosable exist, and consequently for every partition $\lambda$ of 4 other than $\{1,1,1,1\}$ some planar graph fails to be $\lambda$-choosable. On the other hand Zhu proved that every planar graph with chromatic number exactly 3 is $\{1,3\}$-choosable — in contrast to Mirzakhani's 3-chromatic planar graph that is not 4-choosable — and that a planar graph whose dual has a connected spanning Eulerian subgraph (a connected subgraph through all dual vertices in which every degree is even) is $\{2,2\}$-choosable.

The notion is tied to colouring of signed graphs. A signed graph assigns each edge a sign $\sigma(e)\in\{+1,-1\}$; it is $k$-colourable if for every choice of signs there is a mapping $f$ with $f(x)\neq\sigma(xy)f(y)$ on every edge, and $\mathbb{Z}_4$-colourability is the variant where colours are taken from the cyclic group of order 4. Máčajová, Raspaud and Škoviera conjectured that every planar graph is signed 4-colourable; this was disproved by Kardoš and Narboni. Kang and Steffen conjectured that every planar graph is signed $\mathbb{Z}_4$-colourable; Zhu's theorem that every signed $\mathbb{Z}_4$-colourable graph is $\{1,1,2\}$-choosable, combined with Kemnitz and Voigt's construction, disproves it (Zhu also gave a direct counterexample based on a 1973 graph of Wegner). Kündgen and Ramamurthi conjectured that every planar graph is weakly 4-choosable, i.e. colourable from every 4-assignment whose lists are symmetric sets of integers ($i\in L(v)$ implies $-i\in L(v)$); since the positive and negative colours form colour groups, every $\{2,2\}$-choosable graph is weakly 4-choosable, and this conjecture remains open, so positive answers about $\{2,2\}$-choosability of planar subfamilies would be genuine strengthenings of it.

For the $\{1,2\}$ questions the relevant prior facts are: Borodin, Glebov, Raspaud and Salavatipour proved that every planar graph without cycles of lengths 4,5,6,7 is 3-colourable; Montassier conjectured that every planar graph without cycles of lengths 4,5,6 is 3-choosable; and Steinberg's 1976 conjecture that planar graphs without 4- and 5-cycles are 3-colourable was disproved by Cohen-Addad, Hebdige, Král, Li and Salgado, making the $\{1,2\}$-choosability questions natural interpolations between these statements and list-colouring strength. A wheel $W_k$ is obtained from a cycle $C_k$ by adding one vertex adjacent to all cycle vertices, and is odd when $k$ is odd. The line graph of $G$ has the edges of $G$ as its vertices, two being adjacent when the corresponding edges share an endpoint; edge-choosability of $G$ is choosability of its line graph, and the List Colouring Conjecture asserts that every graph's edge choice number equals its edge-chromatic number.

Problem Statement

The problem is the collection of open questions posed in Section 6 of Zhu's 'A refinement of choosability of graphs', all serving one objective: to locate the classical planar families (and their edge-colouring analogues) in the refinement hierarchy between $k$-colourability and $k$-choosability, and to determine the basic structure of that hierarchy. Each item below is independently resolvable, and an item is settled only when every question it states is settled.

(1) Is every triangle-free planar graph $\{1,2\}$-choosable?

(2) Is every planar graph without cycles of lengths 4, 5 and 6 $\{1,2\}$-choosable? Is every planar graph without cycles of lengths 4, 5, 6 and 7 $\{1,2\}$-choosable?

(3) Is every planar graph containing no odd wheel $\{1,1,2\}$-choosable? Is it $\{1,3\}$-choosable? Is it $\{2,2\}$-choosable?

(4) Is every planar graph with chromatic number exactly 3 $\{2,2\}$-choosable?

(5) (Conjecture 2 of the source.) For every integer $s$, is there an integer $k(s)$ such that whenever $k\ge k(s)$, $G$ is edge $k$-colourable, and $\lambda$ is a partition of $k$ in which each part has size at most $s$, then $G$ is edge $\lambda$-choosable — that is, for every assignment of lists of size $k$ to the edges of $G$ whose colour set splits into groups $C_1,\dots,C_q$ with each edge's list taking exactly $k_i$ colours from $C_i$, a proper edge-colouring exists?

(6) (Question 24 of the source.) If $\lambda_1,\lambda_2,\lambda_3$ are pairwise incomparable partitions, must there exist a graph that is $\lambda_1$-choosable and $\lambda_2$-choosable but not $\lambda_3$-choosable? More generally, if $A$ and $B$ are families of partitions of integers such that the partitions in $A\cup B$ are pairwise incomparable, must there exist a graph that is $\lambda$-choosable for all $\lambda\in A$ but not $\lambda$-choosable for all $\lambda\in B$?

References

1. 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 (source paper)
2. Arnfried Kemnitz and Margit Voigt, A note on not-4-list colorable planar graphs, Electronic Journal of Combinatorics 25(2) (2018) #P2.46, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p46
3. František Kardoš and Jonathan Narboni, On the 4-color theorem for signed graphs, European Journal of Combinatorics 91 (2021) 103215, DOI 10.1016/j.ejc.2020.103215, arXiv:1906.05638
4. Hojin Choi and Young Soo Kwon, On t-common list-colorings, Electronic Journal of Combinatorics 24(3) (2017) #P3.32, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p32
5. Yangyan Gu and Xuding Zhu, Girth and λ-choosability of graphs, Journal of Graph Theory 103 (2023) 493–501, DOI 10.1002/jgt.22931, arXiv:2109.00776
6. Kengo Enami and Hikaru Yokoi, On partial order of λ-choosability for planar graphs, Discrete Mathematics 349 (2026) 115115, DOI 10.1016/j.disc.2026.115115
7. Xuding Zhu, List 4-colouring of planar graphs, Journal of Combinatorial Theory, Series B 162 (2023) 1–12, DOI 10.1016/j.jctb.2023.04.001, arXiv:2203.16314
8. Ringi Kim, Seog-Jin Kim and Xuding Zhu, Signed colouring and list colouring of k-chromatic graphs, Journal of Graph Theory 99 (2022) 637–650, DOI 10.1002/jgt.22756
9. Jialu Zhu and Xuding Zhu, Minimum non-chromatic-λ-choosable graphs, Journal of Graph Theory 110 (2025) 283–289, DOI 10.1002/jgt.23267, arXiv:2208.02050
10. Jialu Zhu and Xuding Zhu, Chromatic λ-choosable and λ-paintable graphs, Journal of Graph Theory 98 (2021) 642–652, DOI 10.1002/jgt.22718, arXiv:1910.12509
11. Sounaka Mishra, Rohini S. and Sagar S. Sawant, Complexity of Near-3-Choosability Problem, Graphs and Combinatorics 40, article 104 (2024), DOI 10.1007/s00373-024-02837-x, arXiv:2305.11607
12. Guanwu Liu and Rongxing Xu, Partitioning triangle-free planar graphs into a forest and a linear forest, European Journal of Combinatorics 137 (2026) 104411, DOI 10.1016/j.ejc.2026.104411, arXiv:2510.02038
13. Evan Leonard, Strictly k-colorable graphs, Discrete Mathematics 349 (2026) 114980, DOI 10.1016/j.disc.2026.114980, arXiv:2307.05461
14. Chunqiu Fang and Rongxing Xu, Codegree Thresholds for λ-Choosability of Graphs, arXiv:2608.16740 (2026), https://arxiv.org/abs/2608.16740
15. Yangyan Gu, Yiting Jiang, David R. Wood and Xuding Zhu, Refined list version of Hadwiger's conjecture, arXiv:2209.07013 (2022), https://arxiv.org/abs/2209.07013
16. Margit Voigt, List colourings of planar graphs, Discrete Mathematics 120 (1993) 215–219, DOI 10.1016/0012-365X(93)90579-I
17. Maryam Mirzakhani, A small non-4-choosable planar graph, Bulletin of the Institute of Combinatorics and its Applications 17 (1996) 15–18, zbMATH 0860.05029, https://zbmath.org/890665
18. Carsten Thomassen, Every planar graph is 5-choosable, Journal of Combinatorial Theory, Series B 62 (1994) 180–181, DOI 10.1006/jctb.1994.1062
19. Margit Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Mathematics 146 (1995) 325–328, DOI 10.1016/0012-365X(94)00180-9
20. O. V. Borodin, A. N. Glebov, A. Raspaud and M. R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, Journal of Combinatorial Theory, Series B 93 (2005) 303–311, DOI 10.1016/j.jctb.2004.11.001
21. Mickaël Montassier, A note on the not 3-choosability of some families of planar graphs, Information Processing Letters 99 (2006) 68–71, DOI 10.1016/j.ipl.2005.10.014
22. Vincent Cohen-Addad, Michael Hebdige, Daniel Král, Zhentao Li and Esteban Salgado, Steinberg's conjecture is false, Journal of Combinatorial Theory, Series B 122 (2017) 452–456, DOI 10.1016/j.jctb.2016.07.006, arXiv:1604.05108
23. André Kündgen and Radhika Ramamurthi, Coloring face-hypergraphs of graphs on surfaces, Journal of Combinatorial Theory, Series B 85 (2002) 307–337, DOI 10.1006/jctb.2001.2107
24. Edita Máčajová, André Raspaud and Martin Škoviera, The chromatic number of a signed graph, Electronic Journal of Combinatorics 23(1) (2016) #P1.14, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p14