Irreducible coverings by cliques and Sperner's theorem
type: Item
instance of: scholarly article
title: Irreducible coverings by cliques and Sperner's theorem
zbMATH Open document ID: 1018.05079
published in: The Electronic Journal of Combinatorics
publication date: 2003-05-13T00:00:00Z
full work available at URL: https://eudml.org/doc/122807
full work available at URL: v9i1n11.html
review text: Suppose there is an irreducible covering of the \(n\) vertices of a graph \(G\) by \(n-k\) cliques. The author shows that this implies that the size of the largest clique of \(G\) is at most \(k+1\), if \(k= 2\) or \(3\), and at most \({k\choose [k/2]}\) if \(k\geq 4\). The bounds are best possible if \(n\) is sufficiently large with respect to \(k\).
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1862492
zbMATH Keywords: clique
zbMATH Keywords: irreducible covering
zbMATH Keywords: antichain
zbMATH Keywords: Sperner's theorem
author: Ioan Tomescu
reviewed by: J. W. Moon
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1862492