Homomorphisms to oriented cycles

DOI10.1007/BF01303514zbMath0794.05037MaRDI QIDQ1316647

Xuding Zhu, Hui Shan Zhou, Pavol Hell

Publication date: 18 April 1994

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

characterizationhomomorphismdigraphsoriented cyclemultiplicative cycles

Mathematics Subject Classification ID

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

Related Items

Homomorphisms to oriented paths ⋮ Lattices arising in categorial investigations of Hedetniemi's conjecture ⋮ Multiplicativity of acyclic digraphs ⋮ Complexity of tree homomorphisms ⋮ Homomorphic preimages of geometric paths ⋮ Path homomorphisms ⋮ Duality pairs and homomorphisms to oriented and unoriented cycles ⋮ Multiplicativity of acyclic local tournaments

Cites Work

• Unnamed Item
• On the complexity of colouring by superdigraphs of bipartite graphs
• Symmetric graphs and interpretations
• The effect of two cycles on the complexity of colourings by directed graphs
• The chromatic number of the product of two 4-chromatic graphs is 4
• On the complexity of H-coloring
• Polynomial graph-colorings
• Universality of \(A\)-mote graphs
• Homomorphisms of graphs and of their orientations
• On classes of relations and graphs determined by subobjects and factorobjects
• Homomorphisms to oriented paths
• On the chromatic number of the product of graphs
• The Complexity of Colouring by Semicomplete Digraphs
• On the complexity of the general coloring problem
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
• An approach to hedetniemi's conjecture
• The Categorical Product of Graphs