Badly-covered graphs

We show that the maximum number of different sizes of maximal complete kk-partite induced subgraphs of a graph GG of sufficiently large order nn is at least (n−k+1)−log2(n−k+1)−4(n−k+1)−log2(n−k+1)−4 and at most n−⌊log2(nk!)⌋. 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 K1,kK1,k-free graphs and regular graphs.