Independent Chains in Acyclic Posets

Authors Nika Salia, Christoph Spiegel, Casey Tompkins, Oscar Zamora

Publication date 6 December 2019

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

m a t h c a l G

of equal order, we are interested in the parameter

a (m a t h c a l G) = m i n_{G i n m a t h c a l G} m a x | U | : U s u b s e t e q V, G [U] e x t i s a v e r t e x - d i s j o i n t u n i o n o f c l i q u e s

. We determine the value of this parameter precisely when

m a t h c a l G

is the family of comparability graphs of

n

-element posets with acyclic cover graph. In particular, we show that

a (m a t h c a l G) = (n + o (n)) / l o g_{2} (n)

in this class.

This page was built for publication: Independent Chains in Acyclic Posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330608)