A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs
Abstract
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 ω(G) satisfiesλ1(G)2+λ2(G)2≤ 2(1−1/ω(G))m,where λ1(G)≥ λ2(G)≥⋯≥λ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 η△(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λ1(G)2+λ2(G)2≤ 2(1−1/ω)m+Cω η△(G),where ω=ω(G) andCω=2+2/ω+4ω/(ω−2) (ω≥3).For ω=1,2, no additive error is needed. Since Cω≤ 44/3, a uniform error term (44/3) η△(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 η△(G) in this perturbative framework, and we clarify the relation with bounds expressed in terms of the total number of triangles.
Related
- A characterization of equality in the edge-localized Bollobás-Nikiforov inequality
- A sharp bound for the least signless Laplacian eigenvalue of triangle-free graphs
- Sparse chromatic graphs and the complete-graph triangle bound
- Geometric triangle-free graphs of large chromatic number
- When are random regular triangle-free graphs bipartite?
BibTeX
@article{lu2026robust,
title = {{A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs}},
author = {Yong Lu},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
month = nov,
doi = {10.37236/15969},
url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p27},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs
AU - Yong Lu
PY - 2026
DA - 2026/11/06
JO - The Electronic Journal of Combinatorics
DO - 10.37236/15969
UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p27
AB - 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 ω(G) satisfiesλ_1(G)^2+λ_2(G)^2≤ 2(1−1/ω(G))m,where λ_1(G)≥ λ_2(G)≥⋯≥λ_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 η_△(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λ_1(G)^2+λ_2(G)^2≤ 2(1−1/ω)m+C_ω η_△(G),where ω=ω(G) andC_ω=2+2/ω+4ω/(ω−2) (ω≥3).For ω=1,2, no additive error is needed. Since C_ω≤ 44/3, a uniform error term (44/3) η_△(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 η_△(G) in this perturbative framework, and we clarify the relation with bounds expressed in terms of the total number of triangles.
SN - 1077-8926
ER -