@article { ,
title = {Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs},
abstract = {A k-colouring of a graph G=(V,E) is a mapping c:V→\{1,2,…,k\} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if they differ in colour on just one vertex of G. We introduce a class of k-colourable graphs, which we call k-colour-dense graphs. We show that for each k-colour-dense graph G, the reconfiguration graph of the ℓ-colourings of G is connected and has diameter O(|V|2), for all ℓ≥k+1. We show that this graph class contains the k-colourable chordal graphs and that it contains all chordal bipartite graphs when k=2. Moreover, we prove that for each k≥2 there is a k-colourable chordal graph G whose reconfiguration graph of the (k+1)-colourings has diameter Θ(|V|2).},
doi = {10.1007/s10878-012-9490-y},
eissn = {1573-2886},
issn = {1382-6905},
issue = {1},
journal = {Journal of Combinatorial Optimization},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {132-143},
publicationstatus = {Published},
publisher = {Springer},
volume = {27},
keyword = {Algorithms and Complexity in Durham (ACiD), Reconfigurations, Graph colouring, Graph diameter, Chordal graphs.},
year = {2014},
author = {Bonamy, M and Johnson, M and Lignos, I and Patel, V and Paulusma, D}
}