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

Status partial medium confidence

Conjecture 5 (that $R_6(G)$ has diameter $O(n)$ for planar graphs of girth at least five on $n$ vertices) appears to remain open in full generality. A directly relevant follow-up, arXiv:2112.00631 (SIAM J. Discrete Math. 37(1), 2023), addresses exactly the same setting and proves that the 4-recolouring graph of every planar graph of girth five is connected via a discharging argument, as well as diameter theorems for the recolouring graph; whether the $R_6$ linear-diameter statement is among those results could not be confirmed from the abstract alone, so the conjecture is classified as partially addressed.

Cited literature (1)

• partial 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

  Proves the 4-recolouring graph of every planar graph of girth five is connected (via discharging) and establishes diameter theorems for the recolouring graph in this setting, addressing the same class of graphs as Conjecture 5 though the specific $R_6$ linear-diameter bound could not be confirmed from the abstract.

Reviewer notes. arXiv:2112.00631 (SIAM J. Discrete Math. 37(1):332-350, 2023, DOI 10.1137/21M1463598) is the primary post-statement follow-up; its abstract highlights 4-recolouring connectivity as the main contribution and mentions diameter theorems, but does not explicitly confirm it resolves Conjecture 5. The 2024 Cranston paper in J. Graph Theory on 5-coloring reconfiguration for planar graphs with no short odd cycles may also be relevant but its connection to Conjecture 5 could not be verified (access denied). Author names for arXiv:2112.00631 were not extracted from the fetched abstract.

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