Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
Abstract
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 the choice of a polynomial of degree k and on the eigenvalues of the graph. Currently, optimizing these bounds requires solving several MILPs, which quickly becomes computationally demanding as the graph size or k grows. This computational barrier is a major obstacle to the practical use of these bounds. Moreover, we have a limited theoretical understanding of their performance, even for small k. In this paper, we investigate their optimization and complexity. In particular, we improve the MILP formulations, reducing their computational burden and significantly decreasing the running time. Furthermore, we show that the optimization problems associated with the bounds are solvable in polynomial arithmetic time for every fixed k, given exact spectral input.
Related
- Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
- Improved bounds on the b-chromatic number using the independence and chromatic numbers
- Bounds on the maximum denominator of fractional chromatic numbers
- Clique and chromatic numbers of graph powers: spectral bounds and anticodes
- Multiplicative independence in the sequence of k-generalized Pell numbers
BibTeX
@misc{abiad2026optimization,
title = {{Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers}},
author = {Aida Abiad and Stan van Hoesel and Valentin Michaux},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.00524},
eprint = {2605.00524},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.00524},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
AU - Aida Abiad
AU - Stan van Hoesel
AU - Valentin Michaux
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2605.00524
UR - https://arxiv.org/abs/2605.00524
AB - 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 the choice of a polynomial of degree k and on the eigenvalues of the graph. Currently, optimizing these bounds requires solving several MILPs, which quickly becomes computationally demanding as the graph size or k grows. This computational barrier is a major obstacle to the practical use of these bounds. Moreover, we have a limited theoretical understanding of their performance, even for small k. In this paper, we investigate their optimization and complexity. In particular, we improve the MILP formulations, reducing their computational burden and significantly decreasing the running time. Furthermore, we show that the optimization problems associated with the bounds are solvable in polynomial arithmetic time for every fixed k, given exact spectral input.
ER -