Reconfiguring graph homomorphisms on the sphere

DOI10.1016/j.ejc.2020.103086zbMath1437.05166arXiv1810.01111OpenAlexW3005262254MaRDI QIDQ1987080

Jonathan A. Noel, Jae-Baek Lee, Mark H. Siggers

Publication date: 9 April 2020

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

reconfiguration problem\(H\)-colouringsPSPACE-completness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Mixing is hard for triangle-free reflexive graphs ⋮ Recolouring homomorphisms to triangle-free reflexive graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A dichotomy theorem for circular colouring reconfiguration
• Finding shortest paths between graph colourings
• Square-free graphs are multiplicative
• On the complexity of reconfiguration problems
• Kneser's conjecture, chromatic number, and homotopy
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Gibbs measures and dismantlable graphs
• Recolouring reflexive digraphs
• 4-chromatic graphs with large odd girth
• Introduction to reconfiguration
• Recolouring homomorphisms to triangle-free reflexive graphs
• Independent Set Reconfiguration in Cographs and their Generalizations
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• The complexity of change
• Degree-Constrained Subgraph Reconfiguration is in P
• Homomorphism reconfiguration via homotopy
• Finding paths between 3-colorings
• Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
• Hedetniemi's Conjecture and Strongly Multiplicative Graphs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Kempe equivalence of colourings of cubic graphs

This page was built for publication: Reconfiguring graph homomorphisms on the sphere