Independent Chains in Acyclic Posets

Abstract

We consider the problem of determining the maximum order of an induced vertex-disjoint union of cliques in a graph. More specifically, given some family of graphs $\mathcal{G}$ of equal order, we are interested in the parameter $a(\mathcal{G})={\min }_{G\in \mathcal{G}}\max \{|U|:U\subseteq V,G[U]\text{ is a vertex-disjoint union of cliques}\}$. We determine the value of this parameter precisely when $\mathcal{G}$ is the family of comparability graphs of $n$-element posets with acyclic cover graph. In particular, we show that $a(\mathcal{G})=(n+o(n))/{\log }_2(n)$ in this class.

15 pages, 6 figures