Distant precoloring extension in plane triangle-free graphs

Conjecture 1.4 · arXiv:0911.0885

arXiv Conjecture high confidence— first stated 2020-04-15

Authors: Zdenek Dvorak, Daniel Kral, Robin Thomas

Status open medium confidence

Conjecture 1.4 from arXiv:0911.0885 (Dvořák, Král, Thomas), first posted in 2009 and published in 2020, asserts the existence of an absolute constant d such that any precoloring of pairwise-distant vertices in a triangle-free plane graph extends to a 3-coloring. The source paper reduces it to the simpler Conjecture 1.5 (Theorem 5.1), but no paper resolving either conjecture was found in a wide web search. Related work on flexibility of triangle-free planar graphs (arXiv:1902.02971) and further extensions of Grötzsch's theorem (arXiv:2110.01862) addresses adjacent but distinct questions. The conjecture has been open for over 15 years, making confident assessment of open status moderately uncertain.

Reviewer notes. The conjecture was first posted on arXiv in November 2009 and published in 2020. The source paper itself notes that Conjecture 1.4 is implied by Conjecture 1.5 (via Theorem 5.1). No follow-up paper resolving either conjecture was found. Related work: arXiv:1902.02971 (Dvořák et al., 2021, flexibility of list-colorings for triangle-free planar graphs) and arXiv:2110.01862 (further extensions of Grötzsch's theorem) address neighboring problems but not this specific conjecture. The conjecture is old enough (~15 years) that a resolution may exist but was not surfaced by this search.

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

Conjecture. There exists an absolute constant $d \geq 2$ with the following property. Let $G$ be a plane triangle-free graph, let $S$ be a set of vertices of $G$ and let $\psi : S \to \{1, 2, 3\}$ be an arbitrary function. If the distance between every two vertices of $S$ is at least $d$, then $\psi$ extends to a 3-coloring of $G$.

Context

This is a natural extension of Theorem 1.3 to the case of precolored single vertices, where forbidding separating 4-cycles should not be necessary. The paper shows in Theorem 5.1 that Conjecture 1.4 is implied by the seemingly simpler Conjecture 1.5.

Also stated in

Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies (2020-04-15)

Notes. The paper states that Conjecture 1.5 was subsequently confirmed by Dvořák and Lidický [16], which implies Conjecture 1.4 is also true.

Source paper

Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
Zdenek Dvorak, Daniel Kral, Robin Thomas · 2020-04-15
https://arxiv.org/abs/0911.0885 PDF source