Changjiang Bu

Bollobás–Nikiforov conjecture holds asymptotically almost surely

Bollobás and Nikiforov (J. Combin. Theory Ser. B. 97 (2007) 859-865) conjectured that for a graph G that is not complete, with e ( G ) edges and the clique number ω ( G ) , then λ 1 2 + λ 2 2 ≤ 2 e ( G ) 1 − 1 ω ( G ) , where λ 1 and λ 2 are the largest and the second largest eig...