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 solved high confidence

The final source version records that Dvořák and Lidický proved Conjecture 1.5, while its Theorem 5.1 proves that Conjecture 1.5 implies Conjecture 1.4.

Cited literature (1)

proof Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies (2009)

See linked article · Existing literature or final source version

The final source version records that Dvořák and Lidický proved Conjecture 1.5, while its Theorem 5.1 proves that Conjecture 1.5 implies Conjecture 1.4.

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: This is a literature-status correction rather than an independent proof; the supplied material does not reproduce the proof or an explicit value of d.

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

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.

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