DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 23(2) (2003) 325-332
DOI: 10.7151/dmgt.1205

ON MAXIMAL FINITE ANTICHAINS IN THE HOMOMORPHISM ORDER OF DIRECTED GRAPHS

Jaroslav Nesetril1

Department of Applied Mathematics
and
Institute for Theoretical Computer Science (ITI)
Charles University
Malostranské nám.25, 11800 Praha 1, Czech Republic
e-mail: nesetril@kam.ms.mff.cuni.cz

Claude Tardif2

Department of Mathematics and Statistics
University of Regina
Regina SK, S4S 0A2, Canada
e-mail: tardif@math.uregina.ca

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.