Recoloring bounded treewidth graphs

arXiv1302.3486MaRDI QIDQ6239640FDOQ6239640

Authors: Marthe Bonamy, Nicolas Bousquet 

Publication date: 14 February 2013

Abstract: Let $k$ be an integer. Two vertex $k$-colorings of a graph are emph{adjacent} if they differ on exactly one vertex. A graph is emph{$k$-mixing} if any proper $k$-coloring can be transformed into any other through a sequence of adjacent proper $k$-colorings. Any graph is $(tw+2)$-mixing, where $tw$ is the treewidth of the graph (Cereceda 2006). We prove that the shortest sequence between any two $(tw+2)$-colorings is at most quadratic, a problem left open in Bonamy et al. (2012). Jerrum proved that any graph is $k$-mixing if $k$ is at least the maximum degree plus two. We improve Jerrum's bound using the grundy number, which is the worst number of colors in a greedy coloring.

This page was built for publication: Recoloring bounded treewidth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239640)