Skip to main content

Research Repository

Advanced Search

On the diameter of reconfiguration graphs for vertex colourings

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

On the diameter of reconfiguration graphs for vertex colourings Thumbnail


Authors

M. Bonamy

M. Johnson

I.M. Lignos

V. Patel



Abstract

The reconfiguration graph of the k-colourings of a graph G contains as its vertex set the proper vertex k-colourings of G, and two colourings are joined by an edge in the reconfiguration graph if they differ in colour on just one vertex of G. We prove that for a graph G on n vertices that is chordal or chordal bipartite, if G is k-colourable, then the reconfiguration graph of its ℓ-colourings, for ℓ⩾k+1, is connected and has diameter O(n2). We show that this bound is asymptotically tight up to a constant factor.

Citation

Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2011). On the diameter of reconfiguration graphs for vertex colourings. Electronic Notes in Discrete Mathematics, 38(1), 161-166. https://doi.org/10.1016/j.endm.2011.09.028

Journal Article Type Conference Paper
Publication Date Dec 1, 2011
Deposit Date Dec 6, 2011
Publicly Available Date Mar 28, 2024
Journal Electronic Notes in Discrete Mathematics
Print ISSN 1571-0653
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 38
Issue 1
Pages 161-166
DOI https://doi.org/10.1016/j.endm.2011.09.028
Keywords Reconfiguration, Graph colouring, Graph diameter.
Public URL https://durham-repository.worktribe.com/output/1157671

Files

Accepted Journal Article (240 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Electronic notes in discrete mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Electronic notes in discrete mathematics, 38/1, 2011, 10.1016/j.endm.2011.09.028





You might also like



Downloadable Citations