Skip to Main content Skip to Navigation
Journal articles

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

Marthe Bonamy 1, * Matthew Johnson 2 Ioannis Lignos 2 Viresh Patel 2 Daniël Paulusma 2
* Corresponding author
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A $k$-colouring of a graph $G=(V,E)$ is a mapping $c: V\rightarrow\{1,2,\ldots,k\}$ such that $c(u)\neq 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 \emph{$k$-colour-dense} graphs. We show that for each $k$-colour-dense graph $G$, the reconfiguration graph of the $\ell$-colourings of $G$ is connected and has diameter $O(|V|^2)$, for all $\ell\geq 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 \geq 2$ there is a $k$-colourable chordal graph~$G$ whose reconfiguration graph of the $(k+1)$-colourings has diameter $\Theta(|V|^2)$.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782882
Contributor : Marthe Bonamy <>
Submitted on : Wednesday, January 30, 2013 - 5:31:28 PM
Last modification on : Tuesday, December 10, 2019 - 4:08:04 PM
Long-term archiving on: : Monday, June 17, 2013 - 5:47:18 PM

File

pinching_journal_revised.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, Daniël Paulusma. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, Springer Verlag, 2012, pp.15. ⟨10.1007/s10878-012-9490-y⟩. ⟨lirmm-00782882⟩

Share

Metrics

Record views

358

Files downloads

743