Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

Abstract The k th power of a graph G = ( V , E ) , G k , is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of G k which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.