Hoffman proved that a graph $G$ with eigenvalues $\mu_1 \geqslant \cdots \geqslant \mu_n$ and chromatic number $\chi(G)$ satisfies: \[\chi \geqslant 1 + \kappa\] where $\kappa$ is the smallest integer such that \[\mu_1 + \sum_{i=1}^{\kappa} \mu_{n+1-i} \leqslant 0.\] We strengthen this well known result by proving that $\chi(G)$ can be replaced by the quantum chromatic number, $\chi_q(G)$, where for all graphs $\chi_q(G) \leqslant \chi(G)$ and for some graphs $\chi_q(G)$ is significantly smaller than $\chi(G)$. We also prove a similar result, and investigate implications of these inequalities for the quantum chromatic number of various classes of graphs, which improves many known results. For example, we demonstrate that the Kneser graph $KG_{p,2}$ has $\chi_q = \chi = p - 2$.
@article{10_37236_9295,
author = {Pawel Wocjan and Clive Elphick and Parisa Darbari},
title = {Spectral lower bounds for the quantum chromatic number of a graph. {II}},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/9295},
zbl = {1454.05041},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9295/}
}
TY - JOUR
AU - Pawel Wocjan
AU - Clive Elphick
AU - Parisa Darbari
TI - Spectral lower bounds for the quantum chromatic number of a graph. II
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/9295/
DO - 10.37236/9295
ID - 10_37236_9295
ER -
%0 Journal Article
%A Pawel Wocjan
%A Clive Elphick
%A Parisa Darbari
%T Spectral lower bounds for the quantum chromatic number of a graph. II
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9295/
%R 10.37236/9295
%F 10_37236_9295
Pawel Wocjan; Clive Elphick; Parisa Darbari. Spectral lower bounds for the quantum chromatic number of a graph. II. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9295
