Irreducible coverings by cliques and Sperner's theorem

Ioan Tomescu

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

In this note it is proved that if a graph $G$ of order $n$ has an irreducible covering of its vertex set by $n-k$ cliques, then its clique number $\omega (G)\leq k+1$ if $k=2$ or 3 and $\omega (G)\leq { {k} \choose {\lfloor k/2\rfloor }}$ if $k\geq 4$. These bounds are sharp if $n\geq k+1$ (for $k=2$ or 3) and $n\geq k+ { {k} \choose {\lfloor k/2\rfloor }}$ (for $k\geq 4$).

Détail

DOI : 10.37236/1672

Classification : 05C69, 05C35, 06A07
Mots-clés : clique, irreducible covering, antichain, Sperner's theorem