Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
The inertia bound, introduced by Cvetković in 1971, is a fundamental result in spectral graph theory that provides an upper bound for the independence number of a graph in terms of spectral information about a weighted adjacency matrix of the graph. Recently, this bound has been extended to the so-called inertia-type bounds for estimating the independence and chromatic numbers of graph powers ($k$-independence number and distance-$k$ chromatic number of a graph). These bounds have recently found applications in coding theory and quantum information theory. The inertia-type bounds depend on…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.00524
curl -X POST /api/v1/records/arxiv/2605.00524/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.00524/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'