## Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 670-679 |

Number of pages | 10 |

Journal | Journal of Graph Theory |

Volume | 105 |

Issue number | 4 |

DOIs | |

State | Published - Apr 2024 |

## Keywords

- graph coloring
- graph diameter
- planar graphs
- reconfiguration

## ASJC Scopus subject areas

- Geometry and Topology
- Discrete Mathematics and Combinatorics