Skip to content
DraconiticResearch
Search Sources API
203,948 studies31 sourcesUpdated 1 min ago
PreprintCC BY-NC-SA 4.0arXiv

Localization of the Caro-Wei bound and its applications to bipartiteness

  • Aida Abiad
  • Hitesh Kumar
  • Shivaramakrishna Pragada
Open at sourcePDFDOICite

Abstract

We confirm a conjecture of Brause, Randerath, Rautenbach and Schiermeyer (2016) by proving a localized lower bound on the independence number of a graph that strengthens the classical bounds of Fajtlowicz (1978) and of Caro (1979) and Wei (1981), which in turn settles a conjecture by Bertram and Horák (1996). Our proof is based on a new Motzkin--Straus-type inequality involving local clique numbers and the independence number. We then apply the developed methods to study spectral and algebraic measures of graph bipartiteness. In particular, we extend a theorem of Brandt (1998) on spectral bipartiteness from regular Kr+1-free graphs to all Kr+1-free graphs, we improve a general upper bound for the least signless Laplacian eigenvalue of Kr+1-free graphs, and we disprove a conjecture of de Lima, Nikiforov and Oliveira (2016) in the case of K4-free graphs.

Related

  1. New Pareto Z-eigenvalue localization theorems for tensors with applications
    Licai Shao, Xingong Zhang, Yisheng Song
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. A localization framework for 𝕋m-Invariant Toeplitz Algebras: Applications to Gelfand Theory
    Miguel Angel Rodriguez Rodriguez
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  3. Cheeger constants and bipartiteness ratios of Cayley graphons
    Mugdha Mahesh Pokharanakar
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Spectral bipartiteness in generalized odd graphs of diameter three
    Qi Zhou
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
    Yen-Huan Li, Wei-Fu Tseng
    arXivPreprintarXiv licenceFull textStatisticsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{abiad2026localization,
  title = {{Localization of the Caro-Wei bound and its applications to bipartiteness}},
  author = {Aida Abiad and Hitesh Kumar and Shivaramakrishna Pragada},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.00210},
  eprint = {2609.00210},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.00210},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - Localization of the Caro-Wei bound and its applications to bipartiteness
AU  - Aida Abiad
AU  - Hitesh Kumar
AU  - Shivaramakrishna Pragada
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.00210
UR  - https://arxiv.org/abs/2609.00210
AB  - We confirm a conjecture of Brause, Randerath, Rautenbach and Schiermeyer (2016) by proving a localized lower bound on the independence number of a graph that strengthens the classical bounds of Fajtlowicz (1978) and of Caro (1979) and Wei (1981), which in turn settles a conjecture by Bertram and Horák (1996). Our proof is based on a new Motzkin--Straus-type inequality involving local clique numbers and the independence number. We then apply the developed methods to study spectral and algebraic measures of graph bipartiteness. In particular, we extend a theorem of Brandt (1998) on spectral bipartiteness from regular K_r+1-free graphs to all K_r+1-free graphs, we improve a general upper bound for the least signless Laplacian eigenvalue of K_r+1-free graphs, and we disprove a conjecture of de Lima, Nikiforov and Oliveira (2016) in the case of K_4-free graphs.
ER  -