The Existence of Homomorphisms to Oriented Cycles

Pavol Hell, Xuding Zhu

Type: Article

Publication Date: 1995-05-01

Citations: 27

DOI: https://doi.org/10.1137/s0895480192239992

View Publication

Locations

SIAM Journal on Discrete Mathematics - View

Similar Works

Action	Title	Year	Authors
+	Homomorphisms to oriented paths	1994	Pavol Hell Xuding Zhu
+ PDF Chat	Minimum Cost Homomorphism Dichotomy for Oriented Cycles	2009	Gregory Gutin Arash Rafiey Anders Yeo
+	Minimum Cost Homomorphism Dichotomy for Oriented Cycles	2008	Gregory Gutin Arash Rafiey Anders Yeo
+	Complexity of tree homomorphisms	1996	Pavol Hell Jaroslav Nešetřil Xuding Zhu
+	CLASSIFICATION OF HOMOMORPHISMS TO ORIENTED CYCLES AND OF k -PARTITE SATISFIABILITY ∗	2001	Siam J. Discrete
+ PDF Chat	Duality Pairs and Homomorphisms to Oriented and Unoriented Cycles	2021	Santiago Guzmán-Pro César Hernández‐Cruz
+	Graph Relations and Constrained Homomorphism Partial Orders	2014	Yangjing Long
+	On Counting Homomorphisms to Directed Acyclic Graphs	2006	Martin Dyer Leslie Ann Goldberg Mike Paterson
+	The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs	2012	Pavol Hell Arash Rafiey
+	Minimum cost homomorphisms to oriented cycles with some loops	2009	Mohammad M. Karimi Arvind Gupta
+	Minimum cost homomorphisms to digraphs	2009	Mohammad Mahdi Karimi
+	Compositions of Digraphs: A Survey	2021	Yuefang Sun
+	Duality pairs and homomorphisms to oriented and unoriented cycles	2020	Santiago Guzmán-Pro César Hernández‐Cruz
+	Duality Pairs and Homomorphisms to Oriented and Unoriented Cycles.	2020	Santiago Guzmán-Pro César Hernández‐Cruz
+	Multiplicativity of Oriented Cycles	1994	Pavol Hell Huishan Zhou Xuding Zhu
+	The Spectra of Cycle Prefix Digraphs	2003	Francesc Comellas Margarida Mitjana Riera
+	Hamiltonian cycles and paths through matchings	2005	Denise Amar Evelyne Flandrin Grzegorz Gancarzewicz
+	The Path Partition Conjecture for Oriented Graphs	2006	Jean E. Dunbar Ortrud R. Oellermann
+	Highly Arc-Transitive Digraphs With No Homomorphism Onto Z	2002	Aleksander Malnič Dragan Marušič Norbert Seifter Boris Zgrablić
+	3 Edge complexity and digraphs	2024	Bjørn Kjos-Hanssen

Works That Cite This (18)

Action	Title	Year	Authors
+	A SURVEY ON HEDETNIEMI'S CONJECTURE	1998	Xuding Zhu
+	Complexity of tree homomorphisms	1996	Pavol Hell Jaroslav Nešetřil Xuding Zhu
+	Hereditarily hard H-colouring problems	1995	Jørgen Bang‐Jensen Pavol Hell Gary MacGillivray
+	Homomorphisms to oriented paths	1994	Pavol Hell Xuding Zhu
+ PDF Chat	Minimum Cost Homomorphism Dichotomy for Oriented Cycles	2009	Gregory Gutin Arash Rafiey Anders Yeo
+	A surprising permanence of old motivations (a not-so-rigid story)	2008	Jaroslav Nešetřil
+ PDF Chat	Duality and Polynomial Testing of Tree Homomorphisms	1996	Pavol Hell Jaroslav Nešetřil Xuding Zhu
+	Path homomorphisms	1996	Jaroslav Nešetřil Xuding Zhu
+	On homomorphisms to acyclic local tournaments	1995	Pavol Hell Huishan Zhou Xuding Zhu
+	Homomorphisms and oriented colorings of equivalence classes of oriented graphs	2003	William F. Klostermeyer Gary MacGillivray

Works Cited by This (13)

Action	Title	Year	Authors
+ PDF Chat	Duality and Polynomial Testing of Tree Homomorphisms	1996	Pavol Hell Jaroslav Nešetřil Xuding Zhu
+	Multiplicativity of Oriented Cycles	1994	Pavol Hell Huishan Zhou Xuding Zhu
+	On the complexity of colouring by superdigraphs of bipartite graphs	1992	Jørgen Bang‐Jensen Pavol Hell Gary MacGillivray
+	On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs	1991	Gary MacGillivray
+	The effect of two cycles on the complexity of colourings by directed graphs	1990	Jørgen Bang‐Jensen Pavol Hell
+ PDF Chat	On multiplicative graphs and the product conjecture	1988	Roland Häggkvist Pavol Hell Donald J. Miller Víctor Neumann Lara
+	Homomorphisms to oriented paths	1994	Pavol Hell Xuding Zhu
+	The Complexity of Colouring by Semicomplete Digraphs	1988	Jørgen Bang‐Jensen Pavol Hell Gary MacGillivray
+	Hereditarily hard H-colouring problems	1995	Jørgen Bang‐Jensen Pavol Hell Gary MacGillivray
+	Homomorphisms of graphs and of their orientations	1978	Pavol Hell Jaroslav Ne et il