Localization of the Caro-Wei bound and its applications to bipartiteness
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.00210
curl -X POST /api/v1/records/arxiv/2609.00210/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.00210/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'