Geodesic
Antichains in the homomorphism order of graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 48 (2007) no. 4, pp. 571-583 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $\Bbb G$ and $\Bbb D$, respectively, denote the partially ordered sets of homomorphism classes of finite undirected and directed graphs, respectively, both ordered by the homomorphism relation. Order theoretic properties of both have been studied extensively, and have interesting connections to familiar graph properties and parameters. In particular, the notion of a duality is closely related to the idea of splitting a maximal antichain. We construct both splitting and non-splitting infinite maximal antichains in $\Bbb G$ and in $\Bbb D$. The splitting maximal antichains give infinite versions of dualities for graphs and for directed graphs.
Let $\Bbb G$ and $\Bbb D$, respectively, denote the partially ordered sets of homomorphism classes of finite undirected and directed graphs, respectively, both ordered by the homomorphism relation. Order theoretic properties of both have been studied extensively, and have interesting connections to familiar graph properties and parameters. In particular, the notion of a duality is closely related to the idea of splitting a maximal antichain. We construct both splitting and non-splitting infinite maximal antichains in $\Bbb G$ and in $\Bbb D$. The splitting maximal antichains give infinite versions of dualities for graphs and for directed graphs.
Classification : 05C99, 06A07
Keywords: partially ordered set; homomorphism order; duality; antichain; splitting property 
@article{CMUC_2007_48_4_a1,
     author = {Duffus, D. and Erd\"os, P. L. and Ne\v{s}et\v{r}il, J. and Soukup, L.},
     title = {Antichains in the homomorphism order of graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {571--583},
     year = {2007},
     volume = {48},
     number = {4},
     mrnumber = {2375159},
     zbl = {1199.06008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_2007_48_4_a1/}
}
TY  - JOUR
AU  - Duffus, D.
AU  - Erdös, P. L.
AU  - Nešetřil, J.
AU  - Soukup, L.
TI  - Antichains in the homomorphism order of graphs
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 2007
SP  - 571
EP  - 583
VL  - 48
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMUC_2007_48_4_a1/
LA  - en
ID  - CMUC_2007_48_4_a1
ER  - 
%0 Journal Article
%A Duffus, D.
%A Erdös, P. L.
%A Nešetřil, J.
%A Soukup, L.
%T Antichains in the homomorphism order of graphs
%J Commentationes Mathematicae Universitatis Carolinae
%D 2007
%P 571-583
%V 48
%N 4
%U http://geodesic.mathdoc.fr/item/CMUC_2007_48_4_a1/
%G en
%F CMUC_2007_48_4_a1
Duffus, D.; Erdös, P. L.; Nešetřil, J.; Soukup, L. Antichains in the homomorphism order of graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 48 (2007) no. 4, pp. 571-583. http://geodesic.mathdoc.fr/item/CMUC_2007_48_4_a1/