5-Coloring Reconfiguration of Planar Graphs with No Short Odd Cycles

The coloring reconfiguration graph ${\mathcal{C}}_k(G)$ has as its vertex set all the proper $k$-colorings of $G$, and two vertices in ${\mathcal{C}}_k(G)$ are adjacent if their corresponding $k$-colorings differ on a single vertex. Cereceda conjectured that if an $n$-vertex graph $G$ is $d$-degenerate and $k\ge d+2$, then the diameter of ${\mathcal{C}}_k(G)$ is $O(n^2)$. Bousquet and Heinrich proved that if $G$ is planar and bipartite, then the diameter of ${\mathcal{C}}_5(G)$ is $O(n^2)$. (This proves Cereceda’s Conjecture for every such graph with degeneracy 3.) They also highlighted the particular case of Cereceda’s Conjecture when $G$ is planar and has no 3-cycles. As a partial solution to this problem, we show that the diameter of ${\mathcal{C}}_5(G)$ is $O(n^2)$ for every planar graph $G$ with no 3-cycles and no 5-cycles.