Reconfiguration graph for vertex colourings of weakly chordal graphs

DOI10.1016/J.DISC.2019.111733zbMATH Open1432.05040arXiv1902.08071OpenAlexW2990153367MaRDI QIDQ2286594FDOQ2286594

Authors: Carl Feghali, Jiří Fiala 

Publication date: 22 January 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The reconfiguration graph $R_k(G)$ of the $k$-colourings of a graph $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 show that for each $kgeq3$ there is a $k$-colourable weakly chordal graph $G$ such that $R_{k+1}(G)$ is disconnected. We also introduce a subclass of $k$-colourable weakly chordal graphs which we call $k$-colourable compact graphs and show that for each $k$-colourable compact graph $G$ on $n$ vertices, $R_{k+1}(G)$ has diameter $O(n^2)$. We show that this class contains all $k$-colourable co-chordal graphs and when $k=3$ all $3$-colourable $(P_5,overline{P}_5,C_5)$-free graphs. We also mention some open problems.

Full work available at URL: https://arxiv.org/abs/1902.08071

Recommendations

• Recolouring weakly chordal graphs and the complement of triangle-free graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• A reconfigurations analogue of Brooks' theorem
• On the diameter of reconfiguration graphs for vertex colourings
• Paths between colourings of graphs with bounded tree-width

zbMATH Keywords

colouringreconfigurationweakly chordal graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• The strong perfect graph theorem
• Mixing 3-colourings in bipartite graphs
• Connectedness of the graph of vertex-colourings
• The complexity of change
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• A dichotomy theorem for circular colouring reconfiguration
• Optimizing weakly triangulated graphs
• On Roussel-Rubio-type lemmas and their consequences
• Recoloring graphs via tree decompositions
• Introduction to reconfiguration
• Fast recoloring of sparse graphs
• A reconfigurations analogue of Brooks' theorem and its consequences

Cited In (7)

• Reconfiguration of vertex colouring and forbidden induced subgraphs
• Generating weakly chordal graphs from arbitrary graphs
• Recoloring some hereditary graph classes
• Recolouring weakly chordal graphs and the complement of triangle-free graphs
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Mixing colourings in \(2K_2\)-free graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

This page was built for publication: Reconfiguration graph for vertex colourings of weakly chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286594)