Linear diameter of 6-recoloring, girth-5 planar graphs

Conjecture 5 · arXiv:2006.09269

arXiv Conjecture high confidence— first stated 2020-06-16

Authors: Zdeněk Dvořák, Carl Feghali

Status solved high confidence

The published follow-up arXiv:2112.00631 proves that the 6-recolouring graph of every n-vertex planar graph of girth at least five has diameter O(n), exactly resolving Conjecture 5.

Cited literature (1)

proof Recolouring planar graphs of girth at least five (2021)

not extracted from abstract · SIAM Journal on Discrete Mathematics · arXiv:2112.00631 · doi:10.1137/21M1463598

The published follow-up arXiv:2112.00631 proves that the 6-recolouring graph of every n-vertex planar graph of girth at least five has diameter O(n), exactly resolving Conjecture 5.

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 resolution; the follow-up's discharging proof is not reproduced or independently audited here.

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

Conjecture. If $G$ is a planar graph of girth at least five on $n$ vertices, then $R_6(G)$ has diameter $O(n)$.

Context

Planar graphs of girth at least five are 2-degenerate and can be colored from lists of size three; combining Lemma 2 with Theorem 1 already shows 7 colors suffice for linear diameter. The authors believe this bound can be improved to 6, and suspect that a variation of their Thomassen-type method can be used to prove the conjecture, though several complications arise.

Source paper

A Thomassen-type method for planar graph recoloring
Zdeněk Dvořák, Carl Feghali · 2020-06-16
https://arxiv.org/abs/2006.09269 PDF source