Publication at Faculty of Mathematics and Physics |
2021
Abstract
The reconfiguration graph R-k(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. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that for a planar graph G with n vertices, R-12(G) has diameter at most 6n, and if G is triangle-free, then R-8(G) has diameter at most 4n.
We use a list coloring technique inspired by results of Thomassen to improve on the number of colors, showing that for a planar graph G with n vertices, R-10(G) has diameter at most 8n, and if G is triangle-free, then R-7(G) has diameter at most 7n. (C) 2021 Elsevier Ltd. All rights reserved.