Strengthening a Theorem of Meyniel
Quentin Deschamps, Carl Feghali, František Kardoš, Clément Legrand–Duchesne, Théo Pierron · SIAM Journal on Discrete Mathematics · 2023
Abstract. For an integer [Formula: see text] and a graph [Formula: see text], let [Formula: see text] be the graph that has vertex set all proper [Formula: see text]-colorings of [Formula: see text], and an edge between two vertices [Formula: see text] and [Formula: see text] whenever the coloring [Formula: see text] can be obtained from [Formula: see text] by a single Kempe change. A theorem of Meyniel from 1978 states that [Formula: see text] is connected with diameter [Formula: see text] for every planar graph [Formula: see text]. We significantly strengthen this result by showing that there is a positive constant [Formula: see text] such that [Formula: see text] has diameter [Formula: see text] for every planar graph [Formula: see text].