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
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
