  We give an almost complete characterization of the hardness of $c$-coloring
$\chi$-chromatic graphs with distributed algorithms, for a wide range of models
of distributed computing. In particular, we show that these problems do not
admit any distributed quantum advantage. To do that: 1) We give a new
distributed algorithm that finds a $c$-coloring in $\chi$-chromatic graphs in
$\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}})$ rounds, with $\alpha =
\bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor$. 2) We prove that any distributed
algorithm for this problem requires $\Omega(n^{\frac{1}{\alpha}})$ rounds.
  Our upper bound holds in the classical, deterministic LOCAL model, while the
near-matching lower bound holds in the non-signaling model. This model,
introduced by Arfaoui and Fraigniaud in 2014, captures all models of
distributed graph algorithms that obey physical causality; this includes not
only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL,
even with a pre-shared quantum state.
  We also show that similar arguments can be used to prove that, e.g.,
3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even
for the non-signaling model, and in particular do not admit any quantum
advantage. Our lower-bound arguments are purely graph-theoretic at heart; no
background on quantum information theory is needed to establish the proofs.
