DOI: 10.1002/jgt.23064 ISSN: 0364-9024

5‐Coloring reconfiguration of planar graphs with no short odd cycles

Daniel W. Cranston, Reem Mahmoud
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


The coloring reconfiguration graph has as its vertex set all the proper ‐colorings of , and two vertices in are adjacent if their corresponding ‐colorings differ on a single vertex. Cereceda conjectured that if an ‐vertex graph is ‐degenerate and , then the diameter of is . Bousquet and Heinrich proved that if is planar and bipartite, then the diameter of is . (This proves Cereceda's Conjecture for every such graph with degeneracy 3.) They also highlighted the particular case of Cereceda's Conjecture when is planar and has no 3‐cycles. As a partial solution to this problem, we show that the diameter of is for every planar graph with no 3‐cycles and no 5‐cycles.

More from our Archive