A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs
The Electronic Journal of Combinatorics · 06.11.2026 · 33 (4)
DOI: 10.37236/15969 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 06.11.2026. Verfasst von Yong Lu.
Abstract (Originalsprache)
The Bollobás-Nikiforov (BN) conjecture, in its clique-number form, asserts that every non-complete graph $G$ of order $n$ with $m$ edges and clique number $\omega(G)$ satisfies\[\lambda_1(G)^2+\lambda_2(G)^2\le 2\left(1-\frac1{\omega(G)}\right)m,\]where $\lambda_1(G)\ge \lambda_2(G)\ge\cdots\ge\lambda_n(G)$ are the adjacency eigenvalues of $G$.We prove an unconditional perturbative form for graphs that can be made triangle-free by deleting few edges. Let $\eta_{\triangle}(G)$ be the minimum number of edges whose deletion destroys all triangles of $G$. Every non-complete graph $G$ on at least two vertices satisfies\[\lambda_1(G)^2+\lambda_2(G)^2\le 2\left(1-\frac1\omega\right)m+C_\omega \eta_{\triangle}(G),\]where $\omega=\omega(G)$ and\[C_\omega=2+\frac2\omega+\frac{4\omega}{\omega-2}\qquad (\omega\ge3).\]For $\omega=1,2$, no additive error is needed. Since $C_\omega\le 44/3$, a uniform error term $(44/3) \eta_{\triangle}(G)$ is valid. The emphasis of the result is the explicit finite error that is linear in the edge-deletion distance from the triangle-free class. We also show that the vertex-disjoint triangle packing number cannot replace $\eta_{\triangle}(G)$ in this perturbative framework, and we clarify the relation with bounds expressed in terms of the total number of triangles.
Zitieren
APA
Lu, Y. (2026). A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs. The Electronic Journal of Combinatorics, 33(4). https://doi.org/10.37236/15969
Vancouver
Lu Y. A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs. The Electronic Journal of Combinatorics. 2026;33(4). doi:10.37236/15969
BibTeX
@article{Lu2026,
author = {Lu, Yong},
title = {A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {4},
doi = {10.37236/15969}
}
EUVIMED