A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
From MaRDI portal
Publication:2833252
DOI10.1002/JGT.22000zbMath1350.05034arXiv1501.05800OpenAlexW2963510032MaRDI QIDQ2833252
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
Related Items (22)
Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph ⋮ A polynomial version of Cereceda's conjecture ⋮ Reconfiguring 10-colourings of planar graphs ⋮ Kempe equivalence of 4‐critical planar graphs ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ An update on reconfiguring 10-colorings of planar graphs ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Unnamed Item ⋮ Partitioning a graph into degenerate subgraphs ⋮ Frozen colourings of bounded degree graphs ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Kempe equivalence of colourings of cubic graphs ⋮ Distributed Recoloring ⋮ Frozen (Δ + 1)-colourings of bounded degree graphs ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints
Cites Work
- Unnamed Item
- The complexity of rerouting shortest paths
- Complexity of independent set reconfigurability problems
- Approximability of the subset sum reconfiguration problem
- On the Boolean connectivity problem for Horn relations
- On the complexity of reconfiguration problems
- Reconfiguration of list edge-colorings in a graph
- Shortest paths between shortest paths
- Fast recoloring of sparse graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Some simplified NP-complete graph problems
- On the Grundy and \(b\)-chromatic numbers of a graph
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- Reconfiguration graphs for vertex colourings of chordal and chordal 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
- Vertex partitions and maximum degenerate subgraphs
- New proof of brooks' theorem
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- Minimal reducible bounds for the class of \(k\)-degenerate graphs
This page was built for publication: A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
