List-coloring bounded obstruction for girth-5 planar graphs

Conjecture 1.7 · arXiv:1302.2158

arXiv Conjecture high confidence— first stated 2017-07-05

Authors: Zdenek Dvorak, Daniel Kral, Robin Thomas

Status solved medium confidence

Postle's fixed-surface bound for fixed-list critical girth-five graphs implies the conjecture after singleton lists are replaced by constant-genus three-list forcing gadgets.

Cited literature (1)

proof 3 List Coloring Graphs of Girth at least Five on Surfaces (2017)

Luke Postle · Journal of Combinatorial Theory, Series B · arXiv:1710.06898

Postle's fixed-surface bound for fixed-list critical girth-five graphs implies the conjecture after singleton lists are replaced by constant-genus three-list forcing gadgets.

Read the literature-status audit

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The required input is the uniform fixed-list L-critical theorem, not merely finiteness of underlying choice-critical graphs.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

Conjecture. For every integer $k \geq 5$, there exists an integer $K$ with the following property. Let $G$ be a planar graph of girth at least five, let $C_1, C_2$ be two cycles in $G$ of lengths at most $k$, and for every $v \in V(G)$ let $L(v)$ be a set such that $|L(v)| = 1$ if $v \in V(C_1 \cup C_2)$ and $|L(v)| \geq 3$ otherwise. If there exists no proper coloring $\phi$ of $G$ such that $\phi(v) \in L(v)$ for every $v \in V(G)$, then $G$ has a subgraph $H$ on at most $K$ vertices such that $C_1$ and $C_2$ are subgraphs of $H$ and there exists no proper coloring $\psi$ of $H$ such that $\psi(v) \in L(v)$ for every $v \in V(H)$.

Context

The conjecture is a list-coloring generalisation of the paper's main result (Theorem 1.6). The authors note that an affirmative answer would imply an analogue of Theorem 1.4 for graphs of girth at least five in the list-coloring setting, and that Luke Postle (private communication) believes he has a proof, though it had not yet been written down at the time of submission.

Notes. The PDF extraction renders the final clause with $\phi$ instead of $\psi$; from context the intended quantifier variable in the conclusion is $\psi$, corrected here.

Source paper

Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk
Zdenek Dvorak, Daniel Kral, Robin Thomas · 2017-07-05
https://arxiv.org/abs/1302.2158 PDF source