Independent Chains in Acyclic Posets

2019/12/06 by Nika Salia, Salia, Nika, Christoph Spiegel +5 · 1 citation
Chemistry · Materials Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #History and advancements in chemistry #Synthesis and properties of polymers

paper · pdf · doi:10.48550/arxiv.1912.03288

openalex publication_date 2019/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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_{G ∈ G} 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 acyclic cover graph. In particular, we show that a(G) = (n+o(n))/log₂ (n) in this class.

Cited by

• Packing Independent Cliques in K₄-minor-free Graphs

Related

• On the maximum number of maximum independent sets in connected graphs
• A Set and Collection Lemma
• Maximal independent sets in clique-free graphs
• Monotonic Properties of Collections of Maximum Independent Sets of a Graph
• Critical and Maximum Independent Sets of a Graph