Back to Search
Start Over
5-Coloring Reconfiguration of Planar Graphs with No Short Odd Cycles
- Publication Year :
- 2022
-
Abstract
- 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\geq 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.<br />Comment: 7 pages, 3 figures, corrects a few errors in the previous version
- Subjects :
- Mathematics - Combinatorics
05C15, 05C85, 05C12
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2208.02228
- Document Type :
- Working Paper