Irreducible Coverings by Cliques and Sperner's Theorem

  • Ioan Tomescu

Abstract

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$).

Published
2002-10-22
Article Number
N11