A dichotomy theorem for circular colouring reconfiguration

DOI10.1016/J.TCS.2016.05.015zbMATH Open1345.05026arXiv1508.05573OpenAlexW2963967898MaRDI QIDQ301588FDOQ301588

Authors: Richard C. Brewster, Sean McGuinness, Benjamin Moore, Jonathan A. Noel 

Publication date: 30 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The "reconfiguration problem" for circular colourings asks, given two $(p,q)$-colourings $f$ and $g$ of a graph $G$, is it possible to transform $f$ into $g$ by changing the colour of one vertex at a time such that every intermediate mapping is a $(p,q)$-colouring? We show that this problem can be solved in polynomial time for $2leqp/q<4$ and is PSPACE-complete for $p/qgeq4$. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.

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

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

zbMATH Keywords

homomorphismdichotomygraph colouringPSPACEreconfigurationcircular colouringrecolouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
• Title not available (Why is that?)
• Coloring digraphs with forbidden cycles
• The complexity of change
• Finding paths between 3-colorings
• Mixing homomorphisms, recolorings, and extending circular precolorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Cycles of length 0 modulo 4 in graphs
• Graphs with a cycle of length divisible by three
• Circular colouring and orientation of graphs
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Finding shortest paths between graph colourings
• Homomorphism reconfiguration via homotopy
• A dichotomy theorem for circular colouring reconfiguration
• Star chromatic number
• Title not available (Why is that?)
• Circular chromatic number: A survey
• On the complexity of reconfiguration problems

Cited In (29)

• Graph homomorphism reconfiguration and frozen \(H\)-colorings
• Reconfiguring graph homomorphisms on the sphere
• On girth and the parameterized complexity of token sliding and token jumping
• Algorithms for Coloring Reconfiguration Under Recolorability Constraints
• Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
• 4-Chromatic graphs have at least four cycles of length 0 mod 3
• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• Recolouring homomorphisms to triangle-free reflexive graphs
• Recolouring reflexive digraphs
• Homomorphism reconfiguration via homotopy
• Token sliding on graphs of girth five
• A dichotomy theorem for circular colouring reconfiguration
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Introduction to reconfiguration
• Token sliding on graphs of girth five
• Complexity of coloring reconfiguration under recolorability constraints
• Invitation to combinatorial reconfiguration
• Square-free graphs are multiplicative
• Title not available (Why is that?)
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
• Reconfiguration of homomorphisms to reflexive digraph cycles
• Galactic token sliding
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Cycles in color-critical graphs
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Hamiltonian cycle reconfiguration with answer set programming
• Recongo: bounded combinatorial reconfiguration with answer set programming
• Homomorphism reconfiguration via homotopy
• Hedetniemi's conjecture and strongly multiplicative graphs

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)