Algebraic Bounds for the Independence and Chromatic Number of Graph Powers

The th graph power of a graph =(,) is the graph whose vertex set is and in which two distinct vertices are adjacent if and only if their distance in is at most . The -independence number ⁡() and distance- chromatic number ⁡() are then defined as the independence number and the chromatic number of , respectively. We present a theoretical framework in which a wide range of bounds for the distance- independence and chromatic numbers can be easily obtained and optimized in terms of the eigenvalues of and a degree- 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.