Eigenvalue bounds for the quantum chromatic number of graph powers

Abstract

The quantum chromatic number, a generalization of the chromatic number, was first defined in relation to the nonlocal quantum coloring game. We generalize the former by defining the quantum $k$-distance chromatic number $\chi_{kq}(G)$ of a graph $G$, which can be seen as the quantum chromatic number of the $k$-th power graph, $G^k$, and as generalization of the classical $k$-distance chromatic number $\chi_k(G)$ of a graph. In this paper, we strengthen three classical eigenvalue bounds for the $k$-distance chromatic number by showing they also hold for the quantum counterpart of this parameter. This shows that several bounds by Elphick et al. [J. Combinatorial Theory Ser. A 168, 2019, Electron. J. Comb. 27(4), 2020] hold in the more general setting of distance-$k$ colorings. As a consequence, we obtain several graph classes for which $\chi_{kq}(G)=\chi_{k}(G)$, thus increasing the number of graphs for which the quantum parameter (which is not known to be computable) is known.