Geodesic
On maximal finite antichains in the homomorphism order of directed graphs
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 325-332.

Voir la notice de l'article provenant de la source Library of Science

We show that the pairs T,D_T where T is a tree and D_T its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.
Keywords: chromatic number, homomorphism duality 
@article{DMGT_2003_23_2_a8,
     author = {Nesetril, Jaroslav and Tardif, Claude},
     title = {On maximal finite antichains in the homomorphism order of directed graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {325--332},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a8/}
}
TY  - JOUR
AU  - Nesetril, Jaroslav
AU  - Tardif, Claude
TI  - On maximal finite antichains in the homomorphism order of directed graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 325
EP  - 332
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a8/
LA  - en
ID  - DMGT_2003_23_2_a8
ER  - 
%0 Journal Article
%A Nesetril, Jaroslav
%A Tardif, Claude
%T On maximal finite antichains in the homomorphism order of directed graphs
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 325-332
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a8/
%G en
%F DMGT_2003_23_2_a8
Nesetril, Jaroslav; Tardif, Claude. On maximal finite antichains in the homomorphism order of directed graphs. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 325-332. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a8/

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

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

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

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

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

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

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

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

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

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

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