Nika Salia: Independent Chains in Acyclic Posets

Co-Authors:

Christoph Spiegel, Casey Tompkins, Oscar Zamora;

 

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 G of equal order,

we are interested in the parameter a(G)=min max{|U|:U⊆V,G[U] is a vertex-disjoint union of cliques}.

We determine the value of this parameter precisely when G is the family of comparability graphs of

n-element posets with an acyclic cover graph. In particular, we show that a(G)=(n+o(n))/log_2(n)

in this class.