# Antichains in the homomorphism order of graphs

**Dwight Duffus, Peter L. Erdos,
Jaroslav Nesetril and Lajos Soukup**

Let G and 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 G and in D. The splitting maximal
antichains give infinite versions of dualities for graphs and for directed
graphs.

**Key words and phrases**:

**2000 Mathematics Subject Classification**:
Primary: , Secondary:

Downloading the paper