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 open medium confidence

No paper was found that directly and verifiably proves Conjecture 1.7 from arXiv:1302.2158. Postle's arXiv:1710.06898 (2017) proves a linear isoperimetric bound for 3-list-coloring of graphs of girth at least five on surfaces and finiteness of 4-list-critical graphs of girth at least five on any fixed surface; this machinery is closely related and may imply the conjecture as a corollary for planar graphs, but the direct connection was not confirmed. The three internal references appear to address different conjectures from adjacent papers rather than Conjecture 1.7 specifically.

Cited literature (1)

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

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

Proves a linear isoperimetric bound for 3-list-coloring of girth-at-least-five graphs on surfaces and finiteness of 4-list-critical graphs of girth at least five on any fixed surface, machinery that may imply the bounded-obstruction conclusion of Conjecture 1.7 as a special case for planar graphs; the explicit connection to Conjecture 1.7 was not verified.

Reviewer notes. The source paper notes that Luke Postle (private communication) believed he had a proof at the time of submission. Postle's subsequent arXiv:1710.06898 proves a linear isoperimetric bound for 3-list-coloring of girth-at-least-five graphs, and the published JCTB version appears in ScienceDirect (doi lookup not performed). The conjecture is closely related to the bounded-obstruction / hyperbolic-family framework developed by Postle and Thomas; however, Conjecture 1.7 specifically concerns planar graphs with two precolored cycles of bounded length and 3-element lists elsewhere, and no paper was found that cites or proves it by name within the 5-call budget.

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

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