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.
تحميل البحث