{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:04:39Z","timestamp":1775639079908,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,12,1]],"date-time":"1993-12-01T00:00:00Z","timestamp":754704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1993,12]]},"DOI":"10.1007\/bf01303514","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T08:01:50Z","timestamp":1111737710000},"page":"421-433","source":"Crossref","is-referenced-by-count":15,"title":["Homomorphisms to oriented cycles"],"prefix":"10.1007","volume":"13","author":[{"given":"Pavol","family":"Hell","sequence":"first","affiliation":[]},{"given":"Huishan","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Xuding","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(90)90017-7","volume":"26","author":"J. Bang-Jensen","year":"1990","unstructured":"J. Bang-Jensen, andP. Hell: On the effect of two cycles on the complexity of colouring,Discrete Applied Math. 26 (1990), 1?23.","journal-title":"Discrete Applied Math."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0401029","volume":"1","author":"J. Bang-Jensen","year":"1988","unstructured":"J. Bang-Jensen, P. Hell, andG. MacGillivray: The complexity of colouring by semicomplete digraphs,SIAM J. on Discrete Math. 1 (1988), 281?298.","journal-title":"SIAM J. on Discrete Math."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0012-365X(92)90276-L","volume":"109","author":"J. Bang-Jensen","year":"1992","unstructured":"J. Bang-Jensen, P. Hell, andG. MacGillivray.: On the complexity of colouring by superdigraphs of bipartite graphs.Discrete Math. 109 (1992), 27?44.","journal-title":"Discrete Math."},{"key":"CR4","unstructured":"J. Bang-Jensen, P. Hell, andG. MacGillivray: Hereditarily hard colouring problems, submitted toDiscrete Math."},{"key":"CR5","first-page":"167","volume":"1","author":"S. Burr","year":"1976","unstructured":"S. Burr, P. Erd?s, andL. Lov\ufffdsz: On graphs of Ramsey type,Ars Comb. 1 (1976), 167?190.","journal-title":"Ars Comb."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1002\/jgt.3190090409","volume":"9","author":"D. Duffus","year":"1985","unstructured":"D. Duffus, B. Sands, andR. Woodrow: On the chromatic number of the product of graphs,J. Graph Theory 9 (1985), 487?495.","journal-title":"J. Graph Theory"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02579374","volume":"5","author":"H. El-Zahar","year":"1985","unstructured":"H. El-Zahar, andN. Sauer: The chromatic number of the product of two 4-chromatic graphs is 4,Combinatorica,5 (1985), 121?126.","journal-title":"Combinatorica"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0166-218X(92)90294-K","volume":"35","author":"W. Gutjahr","year":"1992","unstructured":"W. Gutjahr, E. Welzl, andG. Woeginger Polynomial graph colourings,Discrete Applied Math. 35 (1992), 29?46.","journal-title":"Discrete Applied Math."},{"key":"CR9","first-page":"71","volume":"8","author":"R. H\ufffdggkvist","year":"1988","unstructured":"R. H\ufffdggkvist, P. Hell, D. J. Miller, andV. Neumann-Lara: On multiplicative graphs and the product conjecture,Combinatorica 8, (1988), 71?81.","journal-title":"Combinatorica"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1006\/eujc.1993.1004","volume":"14","author":"R. H\ufffdggkvist","year":"1993","unstructured":"R. H\ufffdggkvist, andP. Hell: OnA-mote universal graphs,European J. of Combinatorics 14 (1993), 23?27.","journal-title":"European J. of Combinatorics"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"F. Harary:Graph Theory, Addison Wesley, 1969.","DOI":"10.21236\/AD0705364"},{"key":"CR12","unstructured":"S. Hedetniemi: Homomorphisms and graph automata, University of Michigan Technical Report 03105-44-T, 1966."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1111\/j.1749-6632.1979.tb17773.x","volume":"328","author":"P. Hell","year":"1979","unstructured":"P. Hell: An introduction to the category of graphs.,Annals of the N. Y. Acad. Sc. 328 (1979) 120?136.","journal-title":"Annals of the N. Y. Acad. Sc."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF01300959","volume":"85","author":"P. Hell","year":"1978","unstructured":"P. Hell, andJ. Ne?et?il: Homomorphisms of graphs and their orientations.,Monatshefte f\ufffdr Math. 85 (1978), 39?48.","journal-title":"Monatshefte f\ufffdr Math."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"P. Hell, andJ. Ne?et?il: On the complexity ofH-colouring,J. Combin. Theory B 48 (1990), 92?100.","journal-title":"J. Combin. Theory B"},{"key":"CR16","unstructured":"P. Hell, H. Zhou, andX. Zhu: Multiplicativity of oriented cycles,Combin. Theory B, in print."},{"key":"CR17","unstructured":"P. Hell, andX. Zhu: Homomorphisms to oriented paths,Discrete Math, in print."},{"key":"CR18","unstructured":"P. Hell, andX. Zhu: The existence of homomorphisms to unbalanced, cycles, submitted."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"348","DOI":"10.21136\/CPM.1984.118204","volume":"51","author":"P. Kom\ufffdrek","year":"1984","unstructured":"P. Kom\ufffdrek: Some new good characterizations of directed graphs,?asopis P?st. Mat. 51 (1984), 348?354.","journal-title":"?asopis P?st. Mat."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/0404035","volume":"4","author":"G. MacGillivray","year":"1991","unstructured":"G. MacGillivray: On the complexity of colourings by vertex-transitive and arctransitive digraphs,SIAM J. Discrete Math. 4 (1991), 397?408.","journal-title":"SIAM J. Discrete Math."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(81)90226-6","volume":"51","author":"H. A. Maurer","year":"1981","unstructured":"H. A. Maurer, J. H. Sudborough, andE. Welzl: On the complexity of the general colouring problem,Inform. and Control 51 (1981), 123?145.","journal-title":"Inform. and Control"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"1511","DOI":"10.4153\/CJM-1968-151-x","volume":"20","author":"D. J. Miller","year":"1968","unstructured":"D. J. Miller: The categorical product of graphs,Canad. J. Math. 20 (1968), 1511?1521.","journal-title":"Canad. J. Math."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0012-365X(78)90062-6","volume":"22","author":"J. Ne?et?il","year":"1978","unstructured":"J. Ne?et?il, andA. Pultr: On classes of relations and graphs determined by subobjects and factorobjects,Discrete Math. 22 (1978), 287?300.","journal-title":"Discrete Math."},{"key":"CR24","unstructured":"N. Sauer, andX. Zhu: An approach to Hedetniemi's, conjecture.,J. Graph Theory, to appear."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0095-8956(84)90056-X","volume":"37","author":"E. Welzl","year":"1984","unstructured":"E. Welzl: Symmetric graphs and interpretations,J. Combin. Th. (B) 37 (1984), 235?244.","journal-title":"J. Combin. Th. (B)"},{"key":"CR26","unstructured":"H. Zhou: Homomorphism properties of graph products, Ph.D. thesis, Simon Fraser University, 1988."},{"key":"CR27","unstructured":"X. Zhu: Multiplicative structures, Ph.D. thesis, The University of Calgary, 1990."},{"key":"CR28","unstructured":"X. Zhu: A polynomial algorithm for homomorphisms to oriented cycles, manuscript, 1991."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01303514.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01303514\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01303514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T10:22:42Z","timestamp":1625653362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01303514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["BF01303514"],"URL":"https:\/\/doi.org\/10.1007\/bf01303514","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}