Linear diameter of planar graph reconfigurations

Problem 3 · arXiv:2002.05383

arXiv Problem high confidence— first stated 2020-02-13

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

Status partial medium confidence

Problem 3 asks for the minimum $\kappa$ such that $R_\kappa(G)$ has diameter $O(n)$ for every $n$-vertex planar graph $G$. The source paper establishes $7 \leq \kappa \leq 10$. A 2024 paper (arXiv:2411.00679, EJC 2025) proves a conjecture of Dvo\v{r}\'ak and Feghali in the list-coloring setting, showing that any two 10-list-colorings of a planar graph can be connected by a recoloring sequence of length linear in the number of vertices. The exact minimum $\kappa$ for uniform $k$-colorings of general planar graphs remains open.

Cited literature (1)

partial 10-list Recoloring of Planar Graphs (2024)

unverified · European Journal of Combinatorics · arXiv:2411.00679

Confirms a conjecture of Dvo\v{r}\'ak and Feghali: for any 10-list assignment of a planar graph, any two list-colorings can be connected by a recoloring sequence of length linear in the number of vertices, published in EJC December 2025.

Reviewer notes. The gap 7 \leq \kappa \leq 10 established in the source paper has not been fully closed for general planar graphs. arXiv:2006.09269 ('A Thomassen-type method for planar graph recoloring', June 2020) gives related bounds via a different technique but falls within the same calendar year as the source paper and was not included in since_posted. arXiv:2411.00679 resolves the generalized list-coloring variant. Author names for since_posted entries could not be confirmed within the web-call cap.

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

Problem. What is the minimum integer $\kappa$ such that for every planar graph $G$ with $n$ vertices, $R_{\kappa}(G)$ has diameter $O(n)$?

Context

Planar graphs are 5-degenerate and have maximum average degree less than 6; prior results give $R_8(G)$ diameter $O(n(\log n)^7)$ and $R_{12}(G)$ diameter at most $6n$ for planar $G$. The paper improves the upper bound to $\kappa \leq 10$ via Theorem 4, and an isolated 6-coloring of the icosahedron shows $\kappa \geq 7$; the authors note that $\kappa = 7$ cannot be excluded.

Source paper

An update on reconfiguring $10$-colorings of planar graphs
Zdeněk Dvořák, Carl Feghali · 2020-02-13
https://arxiv.org/abs/2002.05383 PDF source