Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

Bonamy, M; Johnson, M; Lignos, I; Patel, V; Paulusma, D

doi:10.1007/s10878-012-9490-y

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

Bonamy, M; Johnson, M; Lignos, I; Patel, V; Paulusma, D

Authors

M Bonamy

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

I Lignos

V Patel

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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).

Citation

Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27(1), 132-143. https://doi.org/10.1007/s10878-012-9490-y

Journal Article Type	Article
Publication Date	Jan 1, 2014
Deposit Date	Nov 29, 2012
Publicly Available Date	Apr 19, 2013
Journal	Journal of Combinatorial Optimization
Print ISSN	1382-6905
Electronic ISSN	1573-2886
Publisher	Springer
Peer Reviewed	Peer Reviewed
Volume	27
Issue	1
Pages	132-143
DOI	https://doi.org/10.1007/s10878-012-9490-y
Keywords	Reconfigurations, Graph colouring, Graph diameter, Chordal graphs.