Diameter of colorings under Kempe changes
DOI10.1016/j.tcs.2020.05.033zbMath1456.05056OpenAlexW3032033493MaRDI QIDQ5918932
Marc Heinrich, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, Kunihiro Wasa, Marthe Bonamy, Takehiro Ito, Yusuke Kobayashi
Publication date: 1 September 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.05.033
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)
Related Items (2)
Cites Work
- Unnamed Item
- Fairness in academic course timetabling
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Kempe classes and the Hadwiger conjecture
- Perfect product graphs
- Les 5-colorations d'un graphe planaire forment une classe de commutation unique
- On a conjecture of Mohar concerning Kempe equivalence of regular graphs
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Improved bounds for sampling colorings
- The complexity of change
- Finding paths between 3-colorings
- Algorithmic Aspects of Vertex Elimination on Graphs
- Using contracted solution graphs for solving reconfiguration problems.
- A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm
- Parameterized Complexity of Graph Constraint Logic
- New proof of brooks' theorem
- Diameter of colorings under Kempe changes
This page was built for publication: Diameter of colorings under Kempe changes
