×

Antichains in the homomorphism order of graphs. (English) Zbl 1199.06008

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

MSC:

06A07 Combinatorics of partially ordered sets
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: EuDML EMIS