{"id":"arxiv/2609.00210","url":"https://arxiv.org/abs/2609.00210","tags":["math.CO"],"score":0,"title":"Localization of the Caro-Wei bound and its applications to bipartiteness","domain":"math.CO","source":"arxiv","authors":["Aida Abiad","Hitesh Kumar","Shivaramakrishna Pragada"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}