论文标题
特征值边界的独立性和色素数量的优化
Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
论文作者
论文摘要
$ k^{\ text {th}} $ agragr $ g =（v，e）$，$ g^k $的功率是其顶点集为$ v $的图形，并且仅在$ g $中的距离时，只有两个不同的顶点相邻，最多只有$ g $。本文证明了独立数量的各种特征值和$ g^k $的色数，纯粹取决于$ g $的光谱，以及一种方法来优化它们。我们对$ k $独立的数字的界限也适用于其量子对应物，这通常是可计算的参数，从而证明使用整数编程来优化它们是合理的。先前在文献中已知的一些界限是我们主要结果的推论。也出现了界限的无限图。
The $k^{\text{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.
