More tales of Hoffman: bounds for the vector chromatic number of a graph (Q2107750)

The authors prove bounds between parameters related to graph colouring and parameters obtained from graph spectral theory. More specifically, the authors consider two parameters of a graph \(G\) related to the eigenvalues of matrices associated with \(G\), which were obtained respectively in [\textit{L. Silva de Lima} et al., Linear Algebra Appl. 435, No. 10, 2570--2584 (2011; Zbl 1222.05180)] and in [\textit{L. Yu. Kolotilina}, J. Math. Sci., New York 176, No. 1, 44--56 (2011; Zbl 1291.15050); translation from Zap. Nauchn. Semin. POMI 382, 82--103 (2010)]. It was known that both of these parameters are lower bounds for \(\chi(G)\). The main result of this paper is that these parameters are, in fact, also lower bounds for the ``vector chromatic number'' \(\chi_v(G)\) introduced by \textit{D. Karger} et al. [J. ACM 45, No. 2, 246--265 (1998; Zbl 0904.68116)].