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

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 sp...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2022-03, Vol.345 (3), p.112706, Article 112706
Main Authors: Abiad, A., Coutinho, G., Fiol, M.A., Nogueira, B.D., Zeijlemaker, S.
Format: Article
Language:English
Subjects:
Chromatic number
Eigenvalue interlacing
Independence number
Integer programming
k-partially walk-regular
k-power graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2021.112706