The quantum chromatic number 
of a graph 
is a quantum analog of the chromatic
number. It is the minimum number 
of colors for which two separated players can win the 
-coloring
game on 
with certainty using an entangled strategy. In this game, the players are given vertices
and 
of 
which are promised to be equal or adjacent.
They must return colors that agree when 
and differ when 
and 
are adjacent (Cameron et al. 2007).
Classical deterministic strategies for the coloring game are equivalent to ordinary vertex colorings, and therefore
 |
(1)
|
Quantum 2-colorability is exactly the property of being bipartite. Thus a non-bipartite graph satisfies 
, and hence 
whenever 
.
The inequality can be strict. Mančinska and Roberson (2016) considered a 13-vertex Mančinska-Roberson graph 
that is the orthogonality graph of the nonzero vectors
in 
modulo overall sign. This graph is also the Yu-Oh 13-ray graph used in state-independent
Kochen-Specker contextuality (Yu and Oh 2012, Cabello et al. 2016). Adding
an apex vertex to 
gives a 14-vertex Mančinska-Roberson
graph 
with 
and 
(Mančinska and Roberson 2016). Cameron et al. (2007) previously gave
the 18-vertex Cameron-Montanaro-Newman-Severini-Winter
graph 
with the same separation. Lalonde (2025) proved that 
is the smallest possible separation between 
and 
, measured by number of vertices, and in particular that
for every graph 
with at most 13 vertices, and also for 14-vertex graphs with
.
There are also variants such as the approximate and commuting quantum chromatic numbers, usually denoted 
and 
, for which
 |
(2)
|
(Paulsen and Todorov 2015, Lalonde 2025).
Algorithmically, Paulsen et al. (2016) described a semidefinite programming hierarchy converging to 
, while Gribling et al. (2018) placed quantum
graph parameters in a tracial noncommutative polynomial optimization framework, i.e.,
one based on traces of polynomial expressions in noncommuting operator variables,
and gave Lasserre-type semidefinite programming
hierarchies converging to the commuting quantum chromatic number. For small graphs,
Lalonde (2025) also used a recursive obstruction method for proving nonexistence
of low-dimensional orthogonal representations in cases where semidefinite
programming bounds alone were insufficient.
The rank-
quantum chromatic number 
further requires all measurement projectors in
a quantum coloring to have rank exactly 
. Lalonde (2025) gave the 21-vertex Lalonde
graph 
with
 |
(3)
|
and
 |
(4)
|
where 
denotes orthogonal rank. This graph is illustrated
above in a number of bilaterally symmetric embeddings and gives the first provable
separation between the rank-1 and rank-2 quantum chromatic numbers.
