Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Combinatorial Optimization Year : 2012

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

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)$.
Fichier principal
Vignette du fichier
pinching_journal_revised.pdf (158.56 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00782882 , version 1 (30-01-2013)

Identifiers

Cite

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, 2012, pp.15. ⟨10.1007/s10878-012-9490-y⟩. ⟨lirmm-00782882⟩
229 View
511 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More