Recoloring Planar Graphs of Girth at Least Five

DOI10.1137/21M1463598MaRDI QIDQ5883290

Carl Feghali, Benjamin Moore, Marc Heinrich, Valentin Bartier, Théo Pierron, Nicolas Bousquet

Publication date: 30 March 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.00631

zbMATH Keywords

graph coloringplanar graphreconfiguration graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items

Optimally reconfiguring list and correspondence colourings ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast recoloring of sparse graphs
• Mixing 3-colourings in bipartite graphs
• Recoloring graphs via tree decompositions
• A Thomassen-type method for planar graph recoloring
• Reconfiguring colorings of graphs with bounded maximum average degree
• An update on reconfiguring 10-colorings of planar graphs
• Recoloring graphs of treewidth 2
• Introduction to reconfiguration
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• The complexity of change
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Improved Bounds for Randomly Sampling Colorings via Linear Programming
• Islands in Graphs on Surfaces

This page was built for publication: Recoloring Planar Graphs of Girth at Least Five