No Distributed Quantum Advantage for Approximate Graph Coloring

We give an almost complete characterization of the hardness of c-coloring χ-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 χ-chromatic graphs in Õ(n