Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

Marthe Bonamy (), Matthew Johnson (), Ioannis Lignos (), Viresh Patel () and Daniël Paulusma ()
Additional contact information
Marthe Bonamy: Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Matthew Johnson: Durham University
Ioannis Lignos: Durham University
Viresh Patel: Durham University
Daniël Paulusma: Durham University

Journal of Combinatorial Optimization, 2014, vol. 27, issue 1, No 11, 132-143

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

Keywords: Reconfigurations; Graph colouring; Graph diameter; Chordal graphs (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9490-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:27:y:2014:i:1:d:10.1007_s10878-012-9490-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9490-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().