Irreducible Coverings by Cliques and Sperner's Theorem

Ioan Tomescu


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

Full Text: