Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-28T06:06:20.403Z Has data issue: false hasContentIssue false
  • English
  • Français

Path homomorphisms

Published online by Cambridge University Press:  24 October 2008

Jaroslav Nešetřil  and
Xuding Zhu
Jaroslav Nešetřil
Affiliation:
Department of Applied Mathematics, Charles University, Prague
Xuding Zhu
Affiliation:
Department of Mathematics and Statistics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate homomorphisms between finite oriented paths. We demonstrate the surprising richness of this perhaps simplest case of homomorphism between graphs by proving the density theorem for oriented paths. As a consequence every two dimensional countable poset is represented finite paths and their homomorphisms, and every finite dimensional poset is represented finite oriented trees and their homomorphisms. We then consider related problems of universal representability and extendability and on-line representability.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 120 , Issue 2 , August 1996 , pp. 207 - 220
Copyright
Copyright © Cambridge Philosophical Society 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bloom, G. and Burr, S.. On unavoidable digraphs in orientations of graphs. J. Graph Theory 11 (1987), 453–462.Google Scholar
[2]Bang-Jansen, J. and Hell, P.. The effect of two cycles on the complexity of colourings by digraphs. Discrete Applied Math. 26 (1990), 1–23.CrossRefGoogle Scholar
[3]Bang-Jansen, J., Hell, P. and MacGillivray, G.. The complexity of colorings semicomplete digraphs. SIAM J. Discrete Math. 1 (1988), 281–289.CrossRefGoogle Scholar
[4]Bang-Jansen, J., Hell, P. and MacGillivray, G.. On the complexity of colouring by superdigraphs of bipartite graphs. Discrete Math., to appear.Google Scholar
[5]Bang-Jansen, J., Hell, P. and MacGillivray, G.. Hereditarily hard colouring problems, submitted to J. Comput. Systems Science.Google Scholar
[6]Gutjahr, W.. Graph colorings (Ph.D. Thesis, Free University, Berlin, 1991).Google Scholar
[7]Gutjahr, W., Welzl, E. and Woeginger, G.. Polynomial graph colorings. Discrete Applied Math. 35 (1992), 29–46.Google Scholar
[8]Häggkvist, R. P. and Hell, P.. Universality of A-mote graphs. Europ. J. of Combin. 14 (1993), 23–27.Google Scholar
[9]Higman, C.. Ordering by divisibility in abstract algebra. Proc. London Math. Soc. 2 (1952), 326–336.Google Scholar
[10]Häggkvist, R. P.Hell, P., Miller, D. J. and Lara, V. Neuman. On multiplicativite graphs and the product conjecture. Combinatorica 8 (1988), 63–74.CrossRefGoogle Scholar
[11]Hell, P.. An introduction to the category of graphs. Annals of the N.Y. Acad. Sc. 328 (1979), 120–136.Google Scholar
[12]Hell, P. and Nešetřil, J.. On the complexity of H-coloring. J. Combin. Th. (B) 48 (1990), 92–110.CrossRefGoogle Scholar
[13]Hell, P. and Nešetřil, J.. Images of rigid digraphs. Europ. J. Combin., 12 (1991), 33–42.Google Scholar
[14]Hell, P. and Nešetřil, J.. Homomorphisms of graphs and their orientations. Monatshefte für Math. 85 (1978), 39–48.CrossRefGoogle Scholar
[15]Hell, P. and Nešetřil, J.. The core of a graph. Discrete Math. 109 (1992), 117–126.Google Scholar
[16]Hell, P. and Nešetřil, J. and Zhu, X.. Complexity of tree homomorphisms, submitted.Google Scholar
[17]Hell, P. and Nešetřil, J. and Zhu, X.. Duality and polynomial testing of tree homomorphisms. Trans. Amer. Math. Soc., to appear.Google Scholar
[18]Hell, P. and Nešetřil, J. and Zhu, X.. Duality of graph homomorphisms; in Combinatorics, Paul Erdös is Eighty Vol. 2 (Bolyai Society Mathematical Studies, Budapest, 1994).Google Scholar
[19]Hell, P. and Nešetřil, J. and Zhu, X.. The existence of homomorphisms to oriented cycles. SIAM J. on Disc. Math., to appear.Google Scholar
[20]Hell, P., and Zhu, X.. Homomorphisms to oriented paths. Discrete Math., 132 (1994), 107–114.Google Scholar
[21]Hell, P., Zhou, H. and Zhu, X.. Homomorphisms to oriented cycles. Combinatorica 13 (1993), 421–433.Google Scholar
[22]Hell, P., Zhou, H. and Zhu, X.Multiplicativity of oriented cycles. J. Comb. Th. (B) 60 (1994), 239–253.CrossRefGoogle Scholar
[23]Komárek, P.. Some new good characterizations of directed graphs. Časopis Pěst, Mat. 51 (1984), 348–354.CrossRefGoogle Scholar
[24]Maurer, H. A., Sudborough, J. H. and Welzl, E.. On the complexity of the general coloring problem. Inform. and Control 51 (1981), 123–145.CrossRefGoogle Scholar
[25]Nešetřil, J.. Theory of graphs (SNTL (Praha), 1979).Google Scholar
[26]Nešetřil, J. and Pultr, A. On classes of relations and graphs determined subobjects and factorobjects. Discrete Math. 22 (1978), 287–300.Google Scholar
[27]Trotter, W. T.. Dimension theory of partially ordered sets (Johns Hopkins University Press, 1992).Google Scholar
[28]Welzl, E.. Symmetric graphs and interpretations. J. Combin. Th. (B) 37 (1984), 235–244.Google Scholar
[29]Zhu, X.. A polynomial algorithm for homomorphisms to oriented cycles. J. Algorithms (to appear).Google Scholar