Homomorphisms to oriented cycles
type: Item
instance of: scholarly article
title: Homomorphisms to oriented cycles
zbMATH Open document ID: 0794.05037
DOI: 10.1007/BF01303514
author: Xuding Zhu
author: Pavol Hell
author: Huishan Zhou
published in: Combinatorica
publication date: 1994-04-18T00:00:00Z
review text: An oriented cycle is a graph obtained form an undirected cycle by orienting its edges. In the paper the authors give a characterization of those digraphs that admit a homomorphism to a special class of oriented cycles. On the basis of the result they give, in a subsequent paper, a characterization of multiplicative cycles (a graph \(G\) is called multiplicative if the class of graphs which are non-homomorphic to \(G\) is closed with respect to the categorical product).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 522713
zbMATH Keywords: oriented cycle
zbMATH Keywords: characterization
zbMATH Keywords: digraphs
zbMATH Keywords: homomorphism
zbMATH Keywords: multiplicative cycles
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: The effect of two cycles on the complexity of colourings by directed graphs
cites work: The Complexity of Colouring by Semicomplete Digraphs
cites work: On the complexity of colouring by superdigraphs of bipartite graphs
cites work: On the chromatic number of the product of graphs
cites work: The chromatic number of the product of two 4-chromatic graphs is 4
cites work: Polynomial graph-colorings
cites work: Universality of \(A\)-mote graphs
cites work: Q5572939
cites work: Homomorphisms of graphs and of their orientations
cites work: On the complexity of H-coloring
cites work: Homomorphisms to oriented paths
cites work: On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
cites work: On the complexity of the general coloring problem
cites work: The Categorical Product of Graphs
cites work: On classes of relations and graphs determined by subobjects and factorobjects
cites work: An approach to hedetniemi's conjecture
cites work: Symmetric graphs and interpretations
description: scientific article; zbMATH DE number 522713