Recoloring Planar Graphs of Girth at Least Five
Valentin Bartier, Nicolás Bousquet, Carl Feghali, Marc Heinrich, Benjamin R. Moore, Théo Pierron · SIAM Journal on Discrete Mathematics · 2023
Abstract. For a positive integer [Formula: see text], the [Formula: see text]-recoloring graph of a graph [Formula: see text] has as vertex set all proper [Formula: see text]-colorings of [Formula: see text] with two [Formula: see text]-colorings being adjacent if they differ by the color of exactly one vertex. A result of Dyer et al. regarding graphs of bounded degeneracy implies that the 7-recoloring graphs of planar graphs, the 5-recoloring graphs of triangle-free planar graphs and the 4-recoloring graphs planar graphs of girth at least six are connected. On the other hand, there are planar graphs whose 6-recoloring graph is disconnected, triangle-free planar graphs whose 4-recoloring graph is disconnected, and planar graphs of any given girth whose 3-recoloring graph is disconnected. The main result of this paper consists in showing, via a novel application of the discharging method, that the 4-recoloring graph of every planar graph of girth five is connected. This completes the classification of the connectedness of the recoloring graph for planar graphs of given girth. We also prove some theorems regarding the diameter of the recoloring graph of planar graphs.