2020/02/13 by Dvořák, Zdeněk, Feghali, Carl
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2002.05383
The reconfiguration graph Rk(G) for the k-colorings of a graph G has as vertex set the set of all possible proper k-colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that if G is a planar graph with n vertices, then R12(G) has diameter at most 6n. We improve on the number of colors, showing that R10(G) has diameter at most 8n for every planar graph G with n vertices.