A reconfigurations analogue of Brooks' theorem and its consequences

DOI10.1002/JGT.22000zbMATH Open1350.05034arXiv1501.05800OpenAlexW2963510032MaRDI QIDQ2833252FDOQ2833252

Authors: Carl Feghali, Matthew Johnson, Daniël Paulusma 

Publication date: 17 November 2016

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

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.

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

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

zbMATH Keywords

graph coloringBrooks' theoremreconfigurations

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Some simplified NP-complete graph problems
• Mixing 3-colourings in bipartite graphs
• Connectedness of the graph of vertex-colourings
• Finding paths between 3-colorings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Title not available (Why is that?)
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Complexity of independent set reconfigurability problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the complexity of reconfiguration problems
• Shortest paths between shortest paths
• On the Grundy and \(b\)-chromatic numbers of a graph
• Reconfiguration of list edge-colorings in a graph
• The complexity of rerouting shortest paths
• Approximability of the subset sum reconfiguration problem
• On the Boolean connectivity problem for Horn relations
• New proof of brooks' theorem
• Minimal reducible bounds for the class of \(k\)-degenerate graphs
• Fast recoloring of sparse graphs
• 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
• Kempe equivalence of 4‐critical planar graphs
• Partitioning a graph into degenerate subgraphs
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Introduction to 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
• Title not available (Why is that?)
• A polynomial version of Cereceda's conjecture
• Distributed recoloring
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Kempe equivalence of colourings of cubic graphs
• Reconfiguration graph for vertex colourings of weakly chordal 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)