Discussiones Mathematicae Graph Theory 23(2) (2003) 325-332
DOI: https://doi.org/10.7151/dmgt.1205
ON MAXIMAL FINITE ANTICHAINS IN THE HOMOMORPHISM ORDER OF DIRECTED GRAPHS
Jaroslav Nesetril1
Department of Applied Mathematics |
Claude Tardif2
Department of Mathematics and Statistics |
Abstract
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.Keywords: chromatic number, homomorphism duality.
2000 Mathematics Subject Classification: 05C15 (primary: graph coloring) 68R05 (secondary: combinatorics).
References
[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. |
Received 3 May 2002
Revised 27 June 2002
Footnotes:
1Partially supported by the Project LN00A056 of the Czech Ministery of Education and by GAUK 158 grant.
2This
research was done while the second author was visiting the Institute for Theoretical Computer Science (ITI) in the fall of 2000. The support of DIMATIA is gratefully acknowledged.