Elphick–Wocjan clique-number conjecture
For every finite simple graph with vertices, adjacency eigenvalues , clique number , and , prove that .
References
- Stronger Spectral Bound for Clique Number — arXiv — Hareshkumar Jadav, Sudipta Mallik, Akhilesh Panchangam, Ranveer Singh
Source: arXiv
Progress summary
A 2026 paper checks the conjecture for more infinite families and obtains a stronger bound there, but the conjecture for all graphs remains open.
Elphick and Wocjan proposed in 2018 that every graph satisfies , where is the number of vertices, the clique number, and the sum of squared positive adjacency eigenvalues.
Known results
- Triangle-free, weakly perfect, Kneser, and almost all random graphs (Elphick–Wocjan, 2018 and 2021).
- Conference graphs; specified strongly regular graphs; line graphs of complete graphs; Cartesian products; and -regular Ramanujan graphs with (2025).
- The general conjecture is explicitly reported as open (2025).
October 15, 2026 verification classes
Jadav, Mallik, Panchangam, and Singh report a stronger spectral bound that verifies the conjecture for a new infinite graph family. This is a partial advance, not a general proof, and the preprint’s claim has not been independently verified here.
Current status (as of October 2026): The conjecture is verified for many graph classes, including infinite families, but remains open for general graphs; the latest strengthened-family result is unverified.
Solutions 0
No solutions have been posted yet.