On maximal finite antichains in the homomorphism order of directed graphs
Jaroslav Nesetril ; Claude Tardif
Discussiones Mathematicae Graph Theory, Tome 23 (2003), p. 325-332 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We show that the pairs T,DT where T is a tree and DT its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.

Publié le : 2003-01-01
EUDML-ID : urn:eudml:doc:270213 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1205,
     author = {Jaroslav Nesetril and Claude Tardif},
     title = {On maximal finite antichains in the homomorphism order of directed graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {23},
     year = {2003},
     pages = {325-332},
     zbl = {1057.05036},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1205}
}

Jaroslav Nesetril; Claude Tardif. On maximal finite antichains in the homomorphism order of directed graphs. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 325-332. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1205/

[000] [1] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34-38, doi: 10.4153/CJM-1959-003-9. | Zbl 0084.39602

[001] [2] P. Hell, J. Nesetril and X. Zhu, Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc. 348 (1996) 1281-1297, doi: 10.1090/S0002-9947-96-01537-1. | Zbl 0877.05055

[002] [3] P. Hell, H. Zhou and X. Zhu, Homomorphisms to oriented cycles, Combinatorica 13 421-433, doi: 10.1007/BF01303514. | Zbl 0794.05037

[003] [4] P. Hell and X. Zhu, The existence of homomorphisms to oriented cycles, SIAM J. on Disc. Math. 8 (1995) 208-222. | Zbl 0831.05059

[004] [5] P. Komárek, Good characterisations in the class of oriented graphs (in Czech), Ph. D. Thesis (Charles University, Prague, 1987).

[005] [6] P. Komárek, Some new good characterizations for directed graphs, Casopis Pest. Mat. 109 (1984) 348-354. | Zbl 0569.05022

[006] [7] J. Nesetril and A. Pultr, On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978) 287-300, doi: 10.1016/0012-365X(78)90062-6. | Zbl 0388.05039

[007] [8] J. Nesetril and S. Shelah, On the Order of Countable Graphs, ITI Series 200-002 (to appear in European J. Combin.).

[008] [9] J. Nesetril and C. Tardif, Duality Theorems for Finite Structures (Characterizing Gaps and Good Characterizations), J. Combin. Theory (B) 80 (2000) 80-97, doi: 10.1006/jctb.2000.1970.

[009] [10] J. Nesetril and C. Tardif, Density via Duality, Theoret. Comp. Sci. 287 (2002) 585-591, doi: 10.1016/S0304-3975(01)00263-8. | Zbl 1058.05062

[010] [11] J. Nesetril and X. Zhu, Path homomorphisms, Math. Proc. Cambridge Philos. Soc. 120 (1996) 207-220, doi: 10.1017/S0305004100074806. | Zbl 0857.05057