An upper bound on the number of cliques in a graph

Abstract Giving a partial solution to a conjecture of Balas and Yu Networks 19 (1989) 247–235, we prove that if the complement of a graph G on n vertices contains no set of t + 1 pairwise disjoint edges as an induced subgraph, then G has fewer than ( n /2 t ) 2 t maximal complete subgraphs. © 1993 by John Wiley & Sons, Inc.