H-minor-free choosability equal to v−1

Problem 1 · arXiv:2304.04246

arXiv Problem high confidence— first stated 2023-04-09

Authors: Olivier Fischer, Raphael Steiner

Status open high confidence

Problem 1 of arXiv:2304.04246 asks for a structural characterization of the subgraph-closed family of graphs H for which f_\ell(H') = v(H')-1 for all H' \subseteq H. The paper itself (published in Combinatorics, Probability and Computing, Vol. 33, March 2024) provides strong negative evidence by showing that for large graphs H with non-trivial connectivity, f_\ell(H) \geq (1-\varepsilon)(v(H)+\kappa(H)), ruling out many candidate classes. No subsequent paper resolving or significantly advancing Problem 1 was found in the indexed literature as of May 2026.

Reviewer notes. No follow-up paper addressing Problem 1 was found. The source paper was published in Combinatorics, Probability and Computing (online November 2023, print March 2024). The Cambridge Core page for the published article did not list citing papers. The problem is posed in the spirit of perfect graph theory and is likely difficult; the paper's main theorems (Theorems 2 and 4) already sharply limit the positive instances. Conjecture is recent (2023) so absence of follow-up is expected.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Characterize the class $\mathcal{H}$ of graphs $H$ such that $f_\ell(H') = v(H')-1$ for all $H' \subseteq H$.

Context

The authors ask for a structural characterization of graphs $H$ for which the list chromatic number of $H$-minor-free graphs matches the trivial lower bound $v(H)-1$. The problem is posed in the spirit of perfect graph theory, seeking the largest subgraph-closed class with this property; the paper's main results (Theorems 2 and 4) strongly limit the horizon for positive instances.

Source paper

On the choosability of $H$-minor-free graphs
Olivier Fischer, Raphael Steiner · 2023-04-09
https://arxiv.org/abs/2304.04246 PDF source