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

Understand

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 $\chi_q^{(1)}(G)$, which upper bounds the quantum chromatic number, but is defined under stronger constraints.
• We study its relation with the chromatic number $\chi(G)$ and the minimum dimension of orthogonal representations $\xi(G)$.
• It is known that $\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)$.