Graphic sequences that have a realization with large clique number
Dhruv Mubayi · Journal of Graph Theory · 2000
We prove that for k ≥ 5, every (2k + 2)-element graphic sequence of positive terms with sum at least 4k(k − 1) can be realized by a graph containing Kk+1. Also, this bound is sharp. Furthermore, for 2k + 3 ≤ n ≤ k(5k − 11)/(2k − 4), we construct a graphic n-element positive sequence with sum (2k − 4)(2k − 1) + 2(n − 1) that has no realization containing Kk+1. This construction partially answers a question of Erdős et al. in the negative. © John Wiley & Sons, Inc. J Graph Theory 34: 20–29, 2000