Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

Asaf Ferber, Liam Hardiman, Xiaonan Chen

We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree $\Delta$. The first is a simple algorithm that extends the idea of Morris and Song to…