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

A. Abiad; G. Coutinho; M. A. Fiol; B. D. Nogueira; S. Zeijlemaker

doi:10.1016/j.disc.2021.112706

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

A. Abiad, G. Coutinho, M. A. Fiol, B. D. Nogueira, S. Zeijlemaker

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

136 Downloads (Pure)

Abstract

The k^th power of a graph G=(V,E), G^k, 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 G^k 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 language	English
Article number	112706
Number of pages	15
Journal	Discrete Mathematics
Volume	345
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2021.112706
Publication status	Published - Mar 2022

Bibliographical note

Funding Information:
The research of A. Abiad is partially supported by the FWO grant 1285921N . A. Abiad and M.A. Fiol gratefully acknowledge the support from DIAMANT . This research of M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00 . B. Nogueira acknowledges grant PRPQ/ADRC from UFMG . The authors would also like to thank Anurag Bishnoi for noticing a tight family for our bound (19) .

Publisher Copyright:
© 2021

Keywords

k-power graph
Independence number
Chromatic number
Eigenvalue interlacing
k-partially walk-regular
Integer programming

Access to Document

10.1016/j.disc.2021.112706

published versionFinal published version, 444 KB

Cite this

@article{504f3b0aa6b14b3e8fa4176f3377f7c5,

title = "Optimization of eigenvalue bounds for the independence and chromatic number of graph powers",

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.",

keywords = "k-power graph, Independence number, Chromatic number, Eigenvalue interlacing, k-partially walk-regular, Integer programming",

author = "A. Abiad and G. Coutinho and Fiol, {M. A.} and Nogueira, {B. D.} and S. Zeijlemaker",

note = "Funding Information: The research of A. Abiad is partially supported by the FWO grant 1285921N . A. Abiad and M.A. Fiol gratefully acknowledge the support from DIAMANT . This research of M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00 . B. Nogueira acknowledges grant PRPQ/ADRC from UFMG . The authors would also like to thank Anurag Bishnoi for noticing a tight family for our bound (19) . Publisher Copyright: {\textcopyright} 2021",

year = "2022",

month = mar,

doi = "10.1016/j.disc.2021.112706",

language = "English",

volume = "345",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

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

AU - Abiad, A.

AU - Coutinho, G.

AU - Fiol, M. A.

AU - Nogueira, B. D.

AU - Zeijlemaker, S.

N1 - Funding Information: The research of A. Abiad is partially supported by the FWO grant 1285921N . A. Abiad and M.A. Fiol gratefully acknowledge the support from DIAMANT . This research of M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00 . B. Nogueira acknowledges grant PRPQ/ADRC from UFMG . The authors would also like to thank Anurag Bishnoi for noticing a tight family for our bound (19) . Publisher Copyright: © 2021

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.

KW - k-power graph

KW - Independence number

KW - Chromatic number

KW - Eigenvalue interlacing

KW - k-partially walk-regular

KW - Integer programming

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

AN - SCOPUS:85119423460

SN - 0012-365X

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

M1 - 112706

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this