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

Aida Abiad, Gabriel Coutinho, Miquel Angel Fiol, Bruno Nogueira, Sjanne Zeijlemaker

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Article number112706
JournalDiscrete Mathematics
Volume345
Issue number3
DOIs
Publication statusPublished - Mar 2022

Fingerprint

Dive into the research topics of 'Optimization of eigenvalue bounds for the independence and chromatic number of graph powers'. Together they form a unique fingerprint.

Cite this