Badly-covered graphs.

We show that the maximum number of different sizes of maximal complete k -partite induced subgraphs of a graph G of sufficiently large order n is at least ( n − k + 1 ) − log 2 ( n − k + 1 ) − 4 and at most n − ⌊ log 2 ( n k ! ) ⌋ . We analyze some features of the structure of graphs with the maximum possible number of different sizes of maximal independent sets, and give best-possible estimates for K 1 , k -free graphs and regular graphs. [ABSTRACT FROM AUTHOR]