2022/01/19 by Deschamps, Quentin, Feghali, Carl, Kardoš, František +2 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2201.07595
For an integer k ≥ 1 and a graph G, let Kk(G) be the graph that has vertex set all proper k-colorings of G, and an edge between two vertices α and~β whenever the coloring~β can be obtained from α by a single Kempe change. A theorem of Meyniel from 1978 states that K5(G) is connected with diameter O(5|V(G)|) for every planar graph G. We significantly strengthen this result, by showing that there is a positive constant c such that K5(G) has diameter O(|V(G)|c) for every planar graph G.