×

Homomorphisms to oriented cycles. (English) Zbl 0794.05037

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).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C99 Graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Bang-Jensen, andP. Hell: On the effect of two cycles on the complexity of colouring,Discrete Applied Math. 26 (1990), 1-23. · Zbl 0697.05029
[2] J. Bang-Jensen, P. Hell, andG. MacGillivray: The complexity of colouring by semicomplete digraphs,SIAM J. on Discrete Math. 1 (1988), 281-298. · Zbl 0678.05018
[3] J. Bang-Jensen, P. Hell, andG. MacGillivray.: On the complexity of colouring by superdigraphs of bipartite graphs.Discrete Math. 109 (1992), 27-44. · Zbl 0783.05047
[4] J. Bang-Jensen, P. Hell, andG. MacGillivray: Hereditarily hard colouring problems, submitted toDiscrete Math.
[5] S. Burr, P. Erd?s, andL. Lov?sz: On graphs of Ramsey type,Ars Comb. 1 (1976), 167-190.
[6] D. Duffus, B. Sands, andR. Woodrow: On the chromatic number of the product of graphs,J. Graph Theory 9 (1985), 487-495. · Zbl 0664.05019
[7] H. El-Zahar, andN. Sauer: The chromatic number of the product of two 4-chromatic graphs is 4,Combinatorica,5 (1985), 121-126. · Zbl 0575.05028
[8] W. Gutjahr, E. Welzl, andG. Woeginger Polynomial graph colourings,Discrete Applied Math. 35 (1992), 29-46. · Zbl 0761.05040
[9] R. H?ggkvist, P. Hell, D. J. Miller, andV. Neumann-Lara: On multiplicative graphs and the product conjecture,Combinatorica 8, (1988), 71-81.
[10] R. H?ggkvist, andP. Hell: OnA-mote universal graphs,European J. of Combinatorics 14 (1993), 23-27. · Zbl 0799.05063
[11] F. Harary:Graph Theory, Addison Wesley, 1969. · Zbl 0182.57702
[12] S. Hedetniemi: Homomorphisms and graph automata, University of Michigan Technical Report 03105-44-T, 1966.
[13] P. Hell: An introduction to the category of graphs.,Annals of the N. Y. Acad. Sc. 328 (1979) 120-136.
[14] P. Hell, andJ. Ne?et?il: Homomorphisms of graphs and their orientations.,Monatshefte f?r Math. 85 (1978), 39-48. · Zbl 0375.05023
[15] P. Hell, andJ. Ne?et?il: On the complexity ofH-colouring,J. Combin. Theory B 48 (1990), 92-100. · Zbl 0639.05023
[16] P. Hell, H. Zhou, andX. Zhu: Multiplicativity of oriented cycles,Combin. Theory B, in print.
[17] P. Hell, andX. Zhu: Homomorphisms to oriented paths,Discrete Math, in print. · Zbl 0819.05030
[18] P. Hell, andX. Zhu: The existence of homomorphisms to unbalanced, cycles, submitted.
[19] P. Kom?rek: Some new good characterizations of directed graphs,?asopis P?st. Mat. 51 (1984), 348-354.
[20] G. MacGillivray: On the complexity of colourings by vertex-transitive and arctransitive digraphs,SIAM J. Discrete Math. 4 (1991), 397-408. · Zbl 0735.68042
[21] H. A. Maurer, J. H. Sudborough, andE. Welzl: On the complexity of the general colouring problem,Inform. and Control 51 (1981), 123-145. · Zbl 0502.68015
[22] D. J. Miller: The categorical product of graphs,Canad. J. Math. 20 (1968), 1511-1521. · Zbl 0167.21902
[23] J. Ne?et?il, andA. Pultr: On classes of relations and graphs determined by subobjects and factorobjects,Discrete Math. 22 (1978), 287-300. · Zbl 0388.05039
[24] N. Sauer, andX. Zhu: An approach to Hedetniemi’s, conjecture.,J. Graph Theory, to appear. · Zbl 0768.05041
[25] E. Welzl: Symmetric graphs and interpretations,J. Combin. Th. (B) 37 (1984), 235-244. · Zbl 0547.05058
[26] H. Zhou: Homomorphism properties of graph products, Ph.D. thesis, Simon Fraser University, 1988.
[27] X. Zhu: Multiplicative structures, Ph.D. thesis, The University of Calgary, 1990.
[28] X. Zhu: A polynomial algorithm for homomorphisms to oriented cycles, manuscript, 1991.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.