Reconfiguring colorings of graphs with bounded maximum average degree

Abstrakt

The reconfiguration graph R-k(G) for the k-colorings of a graph G has as vertex set the set of all possible k-colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex of G. Let d, k >= 1 be integers such that k >= d + 1.

We prove that for every epsilon > 0 and every graph G with n vertices and maximum average degree d - epsilon, R-k(G) has diameter O(n(log n)(d-1)). This significantly strengthens several existing results. (c) 2020 Elsevier Inc.

All rights reserved.

Klíčová slova

• Graph recoloring
• Sparse graphs