A reconfigurations analogue of Brooks' theorem and its consequences

DOI10.1002/JGT.22000MaRDI QIDQ2833252zbMATH OpenOpenAlexFDO

Authors Carl Feghali, Matthew Johnson, Daniël Paulusma

Publication date 17 November 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.05800, http://dro.dur.ac.uk/16830/1/16830.pdf

zbMATH Keywords

graph coloringBrooks' theoremreconfigurations

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Let $G$ be a simple undirected graph on $n$ vertices with maximum degree~$Delta$. Brooks' Theorem states that $G$ has a $Delta$-colouring unless~$G$ is a complete graph, or a cycle with an odd number of vertices. To recolour $G$ is to obtain a new proper colouring by changing the colour of one vertex. We show an analogue of Brooks' Theorem by proving that from any $k$-colouring, $k>Delta$, a $Delta$-colouring of $G$ can be obtained by a sequence of $O(n^2)$ recolourings using only the original $k$ colours unless $G$ is a complete graph or a cycle with an odd number of vertices, or $k=Delta+1$, $G$ is $Delta$-regular and, for each vertex $v$ in $G$, no two neighbours of $v$ are coloured alike. We use this result to study the reconfiguration graph $R_k(G)$ of the $k$-colourings of $G$. The vertex set of $R_k(G)$ is the set of all possible $k$-colourings of $G$ and two colourings are adjacent if they differ on exactly one vertex. We prove that for $Deltageq3$, $R_{Delta+1}(G)$ consists of isolated vertices and at most one further component which has diameter $O(n^2)$. This result enables us to complete both a structural classification and an algorithmic classification for reconfigurations of colourings of graphs of bounded maximum degree.

Recommendations

• A reconfigurations analogue of Brooks' theorem
• A matroid analogue of a theorem of Brooks for graphs
• scientific article; zbMATH DE number 125481
• scientific article; zbMATH DE number 839292
• A strengthening of Brooks' theorem
• Brooks' Theorem and Beyond
• An analog of Brooks' theorem for dynamic colorings
• scientific article; zbMATH DE number 913268
• On Reay's relaxed Tverberg conjecture and generalizations of Conway's thrackle conjecture
• scientific article; zbMATH DE number 443071

Cites work

• scientific article; zbMATH DE number 2159660 (Why is no real title available?)
• Approximability of the subset sum reconfiguration problem
• Complexity of independent set reconfigurability problems
• 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
• Minimal reducible bounds for the class of \(k\)-degenerate graphs
• Mixing 3-colourings in bipartite graphs
• New proof of brooks' theorem
• On the Boolean connectivity problem for Horn relations
• On the Grundy and \(b\)-chromatic numbers of a graph
• On the complexity of reconfiguration problems
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• Some simplified NP-complete graph problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of rerouting shortest paths
• Vertex partitions and maximum degenerate subgraphs

Cited in

(27)

• Reconfiguring graph homomorphisms on the sphere
• Recognizing Graphs Close to Bipartite Graphs
• Using contracted solution graphs for solving reconfiguration problems
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• Frozen \((\Delta+1)\)-colourings of bounded degree graphs
• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• Partitioning a graph into degenerate subgraphs
• Introduction to reconfiguration
• Kempe equivalence of 4‐critical planar graphs
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Complexity of coloring reconfiguration under recolorability constraints
• An update on reconfiguring 10-colorings of planar graphs
• Reconfiguring colorings of graphs with bounded maximum average degree
• A reconfigurations analogue of Brooks' theorem
• Frozen colourings of bounded degree graphs
• Reconfiguring 10-colourings of planar graphs
• Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring
• A polynomial version of Cereceda's conjecture
• scientific article; zbMATH DE number 7525461 (Why is no real title available?)
• Distributed recoloring
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Kempe equivalence of colourings of cubic graphs
• Decremental optimization of vertex-coloring under the reconfiguration framework
• Brooks' Theorem and Beyond
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs

This page was built for publication: A reconfigurations analogue of Brooks' theorem and its consequences

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