Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

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

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.
• Public URL: https://durham-repository.worktribe.com/output/1468666