The Bollobás–Nikiforov conjecture for K4K_4-free graphs

Let GG be a K4K_4-free graph with mm edges, and let

λ1(G)λ2(G)λn(G)\lambda_1(G)\geq\lambda_2(G)\geq\cdots\geq\lambda_n(G)

be the adjacency eigenvalues of GG. Bollobás–Nikiforov conjecture for K4K_4-free graphs. If GK3G\neq K_3, then

λ12(G)+λ22(G)4m3.\lambda_1^2(G)+\lambda_2^2(G)\leq \frac{4m}{3}.

This is the unresolved K4K_4-free specialization of the full conjecture. The source proves the bound for complete multipartite graphs and for sufficiently large dense K4K_4-free graphs, leaving cases with chromatic number at least four and m=o(n2)m=o(n^2) or small nn open.

Sources & referencesView supporting material

Primary source

Piero Giacomelli, “The Bollobás–Nikiforov Conjecture for Complete Multipartite Graphs and Dense K_4-Free Graphs”, arXiv:2603.26379 (2026).

Additional references

12 papers in this index state this conjecture (2019–2026). The statement above is taken from the most recent of them; the others are arXiv:2512.01409, arXiv:2511.15431, arXiv:2501.07137, arXiv:2411.08184, arXiv:2309.08184, arXiv:2304.00716, arXiv:2204.09870, arXiv:2111.03309, arXiv:2109.04599, arXiv:2104.12171, arXiv:1910.12474.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.