Conference 2021
Top image

Program LNMB conference
Invited Speakers
PhD student pitches
Return to LNMB Site

Sjanne Zeijlemaker (Eindhoven UT) - Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
Supervisor: Aida Abiad
Recorded full presentation

The kth power of a graph G is the graph in which two distinct vertices are adjacent if their distance in G is at most k. The independence number and chromatic number of a kth graph power are known as the k-independence and k-chromatic number. In this talk, we prove and optimize various eigenvalue bounds for these parameters which purely depend on the spectrum of G. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general.