2020/06/16 by Dvořák, Zdeněk, Feghali, Carl
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2006.09269
The reconfiguration graph Rk(G) for the k-colorings of a graph G has as vertices all possible k-colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex. We use a list coloring technique inspired by results of Thomassen to prove that for a planar graph G with n vertices, R10(G) has diameter at most 8n, and if G is triangle-free, then R7(G) has diameter at most 7n.