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
* Auteur correspondant
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)$.
Type de document :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2012, pp.15. 〈10.1007/s10878-012-9490-y〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782882
Contributeur : Marthe Bonamy <>
Soumis le : mercredi 30 janvier 2013 - 17:31:28
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : lundi 17 juin 2013 - 17:47:18

Fichier

pinching_journal_revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

224