TY - JOUR

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

AU - Abiad, Aida

AU - Coutinho, Gabriel

AU - Fiol, Miquel Angel

AU - Nogueira, Bruno

AU - Zeijlemaker, Sjanne

PY - 2022/3

Y1 - 2022/3

N2 - The kth power of a graph G=(V,E), Gk, 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 Gk 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.

AB - The kth power of a graph G=(V,E), Gk, 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 Gk 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.

UR - http://www.scopus.com/inward/record.url?scp=85119423460&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112706

DO - 10.1016/j.disc.2021.112706

M3 - Article

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 3

M1 - 112706

ER -