Reconfiguration graph for vertex colourings of weakly chordal graphs

DOI10.1016/J.DISC.2019.111733MaRDI QIDQ2286594zbMATH OpenOpenAlexFDO

Authors Carl Feghali, Jiří Fiala

Publication date 22 January 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

colouringreconfigurationweakly chordal graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

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

Cited in

(11)

• Recolouring weakly chordal graphs and the complement of triangle-free graphs
• Mixing colourings in 2K₂-free graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• On the diameter of reconfiguration graphs for vertex colourings
• Generating weakly chordal graphs from arbitrary graphs
• Reconfiguration of vertex colouring and forbidden induced subgraphs
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Recoloring some hereditary graph classes
• Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs
• Recoloring via modular decomposition
• Reconfiguration graphs for vertex colorings of P₅-free 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)