On maximal finite antichains in the homomorphism order of directed graphs

• Autorzy: Jaroslav Nesetril , Claude Tardif
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

chromatic number; homomorphism duality

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 68R05: Combinatorics

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2003
• Tom: 23
• Numer: 2
• Strony: 325-332

Daty

wydano

2003

otrzymano

2002-05-03

poprawiono

2002-06-27

Twórcy

autor

Jaroslav Nesetril

• Department of Applied Mathematics, Charles University, Malostranské nám.25, 11800 Praha 1, Czech Republic
• Institute for Theoretical Computer Science (ITI), Charles University, Malostranské nám.25, 11800 Praha 1, Czech Republic

autor

Claude Tardif

• Department of Mathematics and Statistics, University of Regina, Regina SK, S4S 0A2, Canada

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1205