Algebraic Bounds for the Independence and Chromatic Number of Graph Powers

Abstract. The [Formula: see text]th graph power [Formula: see text] of a graph [Formula: see text] is the graph whose vertex set is [Formula: see text] and in which two distinct vertices are adjacent if and only if their distance in [Formula: see text] is at most [Formula: see text]. The [Formula: see text]-independence number [Formula: see text] and distance-[Formula: see text] chromatic number [Formula: see text] are then defined as the independence number and the chromatic number of [Formula: see text], respectively. We present a theoretical framework in which a wide range of bounds for the distance-[Formula: see text] independence and chromatic numbers can be easily obtained and optimized in terms of the eigenvalues of [Formula: see text] and a degree-[Formula: see text] polynomial. We demonstrate the power of this method to derive sharp eigenvalue bounds for the two graph parameters. Moreover, we also show that several existing algebraic bounds fall in the proposed framework. Our approach is based on a combination of semidefinite programming and polynomial methods with spectral techniques.