Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers

Aida Abiad, Stan van Hoesel, Valentin Michaux

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…