Publikace na Matematicko-fyzikální fakulta |
2020
Abstrakt
The reconfiguration graph R-k(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 R-12(G) has diameter at most 6n.
We improve on the number of colors, showing that R-10(G) has diameter at most 8n for every planar graph G with n vertices.