The Existence of Homomorphisms to Oriented Cycles

DOI10.1137/S0895480192239992MaRDI QIDQ4837649zbMATH OpenOpenAlexFDO

Authors Xuding Zhu, Pavol Hell

Publication date 12 February 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480192239992

zbMATH Keywords

backward arcscomputational complexitydigraphsforward arcshomomorphismNP-completeoriented cycleoriented path

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph theory (05C99)

Recommendations

• Homomorphisms to oriented cycles
• Homomorphisms to oriented paths
• Homomorphisms to powers of digraphs
• A Polynomial Algorithm for Homomorphisms to Oriented Cycles

Cited in

(22)

• A surprising permanence of old motivations (a not-so-rigid story)
• Homomorphisms to oriented cycles
• Mutiplicativity of oriented cycles
• Homomorphisms to oriented paths
• Homomorphisms to powers of digraphs
• The complexity of restricted graph homomorphisms
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Homomorphic preimages of geometric paths
• Complexity of tree homomorphisms
• Reconfiguration of homomorphisms to reflexive digraph cycles
• Duality pairs and homomorphisms to oriented and unoriented cycles
• Classification of homomorphisms to oriented cycles and of k-partite satisfiability
• Minimum Cost Homomorphism Dichotomy for Oriented Cycles
• On the Nonmultiplicativity of Oriented Cycles
• scientific article; zbMATH DE number 2061631 (Why is no real title available?)
• A Polynomial Algorithm for Homomorphisms to Oriented Cycles
• scientific article; zbMATH DE number 841621 (Why is no real title available?)
• Algebra and the complexity of digraph CSPs: a survey
• Characterization of the Homomorphic Preimages of Certain Oriented Cycles
• Dualities for Constraint Satisfaction Problems
• Homomorphically full oriented graphs
• Minimum cost homomorphism dichotomy for oriented cycles

This page was built for publication: The Existence of Homomorphisms to Oriented Cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4837649)