A dichotomy theorem for circular colouring reconfiguration
From MaRDI portal
(Redirected from Publication:301588)
Abstract: The "reconfiguration problem" for circular colourings asks, given two -colourings and of a graph , is it possible to transform into by changing the colour of one vertex at a time such that every intermediate mapping is a -colouring? We show that this problem can be solved in polynomial time for and is PSPACE-complete for . This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.
Recommendations
- scientific article; zbMATH DE number 1990691
- Circular colouring and graph homomorphism
- Circular coloring of planar digraphs
- An analogue of Hajós' theorem for the circular chromatic number
- On the diameter of reconfiguration graphs for vertex colourings
- Generalized circular colouring of graphs
- Circular colouring and algebraic no-homomorphism theorems
- Circular coloring and Mycielski construction
- Total colorings of circulant graphs
- On the complexity of the circular chromatic number
Cites work
- scientific article; zbMATH DE number 3767009 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- A dichotomy theorem for circular colouring reconfiguration
- Circular chromatic number: A survey
- Circular colouring and orientation of graphs
- Coloring digraphs with forbidden cycles
- Cycles of length 0 modulo 4 in graphs
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Finding shortest paths between graph colourings
- Graphs with a cycle of length divisible by three
- Homomorphism reconfiguration via homotopy
- Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
- Mixing homomorphisms, recolorings, and extending circular precolorings
- On the complexity of reconfiguration problems
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- Star chromatic number
- The complexity of change
Cited in
(29)- Recolouring homomorphisms to triangle-free reflexive graphs
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- Homomorphism reconfiguration via homotopy
- Reconfiguration of homomorphisms to reflexive digraph cycles
- Square-free graphs are multiplicative
- Graph homomorphism reconfiguration and frozen \(H\)-colorings
- Cycles in color-critical graphs
- Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
- Hamiltonian cycle reconfiguration with answer set programming
- Recongo: bounded combinatorial reconfiguration with answer set programming
- Reconfiguring graph homomorphisms on the sphere
- Invitation to combinatorial reconfiguration
- 4-Chromatic graphs have at least four cycles of length 0 mod 3
- Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
- Complexity of coloring reconfiguration under recolorability constraints
- A dichotomy theorem for circular colouring reconfiguration
- On girth and the parameterized complexity of token sliding and token jumping
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- Recolouring reflexive digraphs
- Introduction to reconfiguration
- Homomorphism reconfiguration via homotopy
- Galactic token sliding
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- Hedetniemi's conjecture and strongly multiplicative graphs
- scientific article; zbMATH DE number 7765402 (Why is no real title available?)
- Algorithms for Coloring Reconfiguration Under Recolorability Constraints
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- Token sliding on graphs of girth five
- Token sliding on graphs of girth five
This page was built for publication: A dichotomy theorem for circular colouring reconfiguration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q301588)
