A dichotomy theorem for circular colouring reconfiguration

DOI10.1016/j.tcs.2016.05.015zbMath1345.05026arXiv1508.05573OpenAlexW2963967898MaRDI QIDQ301588

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

Publication date: 30 June 2016

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

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

zbMATH Keywords

homomorphismgraph colouringdichotomyPSPACEreconfigurationcircular colouringrecolouring

Mathematics Subject Classification ID

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

Related Items (22)

Cycles in color-critical graphs ⋮ A dichotomy theorem for circular colouring reconfiguration ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Invitation to combinatorial reconfiguration ⋮ Square-free graphs are multiplicative ⋮ Token sliding on graphs of girth five ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Galactic token sliding ⋮ Token sliding on graphs of girth five ⋮ Recolouring homomorphisms to triangle-free reflexive graphs ⋮ Unnamed Item ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Recolouring reflexive digraphs ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Reconfiguration of homomorphisms to reflexive digraph cycles ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ Introduction to reconfiguration ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
• A dichotomy theorem for circular colouring reconfiguration
• Coloring digraphs with forbidden cycles
• On the complexity of reconfiguration problems
• 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
• The complexity of change
• Finding Shortest Paths Between Graph Colourings
• Homomorphism reconfiguration via homotopy
• Finding paths between 3-colorings
• Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
• Star chromatic number
• Circular chromatic number: A survey

This page was built for publication: A dichotomy theorem for circular colouring reconfiguration