Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 54 min ago
PreprintCC BY 4.0arXiv

Stronger Spectral Bound for Clique Number

  • Hareshkumar Jadav
  • Sudipta Mallik
  • Akhilesh Panchangam
  • Ranveer Singh
Open at sourcePDFDOICite

Abstract

Given an integer k, deciding whether a graph has a clique of size k is an NP-complete problem. Wilf's inequality provides a spectral lower bound for the clique number of a graph. Strengthening this bound, Elphick and Wocjan proposed a conjecture in 2018 using positive adjacency eigenvalues. In this paper, we present an infinite family of graphs for which the Elphick and Wocjan conjecture is true. We find a stronger spectral lower bound for the clique number for this family of graphs.

Related

  1. A stronger upper bound on the D-chromatic index
    Lin Tian, Runze Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Local Clique Covers and Chromatic Number
    Akbar Davoodi
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Bounded chromatic number of graphs with small clique number and large minimum degree
    Jiaao Li, Xinyuan Li
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
    Andrea Munaro
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Clique Number of Tournaments II
    Guillaume Aubian, Samuel Coulomb
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{jadav2026stronger,
  title = {{Stronger Spectral Bound for Clique Number}},
  author = {Hareshkumar Jadav and Sudipta Mallik and Akhilesh Panchangam and Ranveer Singh},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.21388},
  eprint = {2610.21388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21388},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Stronger Spectral Bound for Clique Number
AU  - Hareshkumar Jadav
AU  - Sudipta Mallik
AU  - Akhilesh Panchangam
AU  - Ranveer Singh
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.21388
UR  - https://arxiv.org/abs/2610.21388
AB  - Given an integer k, deciding whether a graph has a clique of size k is an NP-complete problem. Wilf's inequality provides a spectral lower bound for the clique number of a graph. Strengthening this bound, Elphick and Wocjan proposed a conjecture in 2018 using positive adjacency eigenvalues. In this paper, we present an infinite family of graphs for which the Elphick and Wocjan conjecture is true. We find a stronger spectral lower bound for the clique number for this family of graphs.
ER  -