# On maximal finite antichains in the homomorphism order of directed graphs

Jaroslav Nesetril; Claude Tardif

Discussiones Mathematicae Graph Theory (2003)

- Volume: 23, Issue: 2, page 325-332
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJaroslav Nesetril, and Claude Tardif. "On maximal finite antichains in the homomorphism order of directed graphs." Discussiones Mathematicae Graph Theory 23.2 (2003): 325-332. <http://eudml.org/doc/270213>.

@article{JaroslavNesetril2003,

abstract = {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.},

author = {Jaroslav Nesetril, Claude Tardif},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {chromatic number; homomorphism duality; tree; homomorphism ordering},

language = {eng},

number = {2},

pages = {325-332},

title = {On maximal finite antichains in the homomorphism order of directed graphs},

url = {http://eudml.org/doc/270213},

volume = {23},

year = {2003},

}

TY - JOUR

AU - Jaroslav Nesetril

AU - Claude Tardif

TI - On maximal finite antichains in the homomorphism order of directed graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2003

VL - 23

IS - 2

SP - 325

EP - 332

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

LA - eng

KW - chromatic number; homomorphism duality; tree; homomorphism ordering

UR - http://eudml.org/doc/270213

ER -

## References

top- [1] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34-38, doi: 10.4153/CJM-1959-003-9. Zbl0084.39602
- [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. Zbl0877.05055
- [3] P. Hell, H. Zhou and X. Zhu, Homomorphisms to oriented cycles, Combinatorica 13 421-433, doi: 10.1007/BF01303514. Zbl0794.05037
- [4] P. Hell and X. Zhu, The existence of homomorphisms to oriented cycles, SIAM J. on Disc. Math. 8 (1995) 208-222. Zbl0831.05059
- [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. Zbl0569.05022
- [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. Zbl0388.05039
- [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. Zbl1058.05062
- [11] J. Nesetril and X. Zhu, Path homomorphisms, Math. Proc. Cambridge Philos. Soc. 120 (1996) 207-220, doi: 10.1017/S0305004100074806. Zbl0857.05057

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.