Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number

The quantum chromatic number of a graph G is sandwiched between its chromatic number and its clique number, which are well-known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number χ_q⁽¹⁾(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number χ(G) and the minimum dimension of orthogonal representations ξ(G). It is known that ξ(G) ≤ χ_q⁽¹⁾(G) ≤ χ(G). We answer three open questions about these relations: we give a necessary and sufficient condition to have ξ(G) = χ_q⁽¹⁾(G), we exhibit a class of graphs such that ξ(G) ≤ χ_q⁽¹⁾(G), and we give a necessary and sufficient condition to have χ_q⁽¹⁾(G) ≤ χ(G). Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of contextuality of physical theories and, more recently, in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis et al on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.