Sergey Bravyi, Anirban Chowdhury, et al.
Nature Physics
Let χ(G) denote the chromatic number of a graph and χv(G) denote the vector chromatic number. For all graphs χv(G) ≤ χ(G) and for some graphs χv(G) ≪ χ(G). Galtman proved that Hoffman's well-known lower bound for χ(G) is in fact a lower bound for χv(G). We prove that two more spectral lower bounds for χ(G) are also lower bounds for χv(G). We then use one of these bounds to derive a new characterization of χv(G).
Sergey Bravyi, Anirban Chowdhury, et al.
Nature Physics
Pawel Wocjan, Clive Elphick, et al.
Electronic Journal of Linear Algebra
Pawel Wocjan, Kristan Temme
Commun. Math. Phys.
Clive Elphick, William Linz, et al.
Linear Algebra and Its Applications