Recolouring reflexive digraphs

DOI10.1016/J.DISC.2018.03.006zbMath1384.05083OpenAlexW2795132661WikidataQ130046463 ScholiaQ130046463MaRDI QIDQ1744757

Jae-Baek Lee, Richard C. Brewster, Mark H. Siggers

Publication date: 19 April 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2018.03.006

zbMATH Keywords

homomorphismsrecolouringreflexive digraphshom-graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Recolouring homomorphisms to triangle-free reflexive graphs ⋮ Recolouring reflexive digraphs ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Reconfiguration of homomorphisms to reflexive digraph cycles

Cites Work

• A dichotomy theorem for circular colouring reconfiguration
• Reflexive digraphs with near unanimity polymorphisms
• Extending precolourings of circular cliques
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Recolouring reflexive digraphs
• Homomorphism reconfiguration via homotopy
• Finding paths between 3-colorings
• A polynomial-time algorithm for near-unanimity graphs
• Gray code numbers for graphs
• Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings

This page was built for publication: Recolouring reflexive digraphs