Paper detail

Simple vertex coloring algorithms

Given a graph $G$ with $n$ vertices and maximum degree $Δ$, it is known that $G$ admits a vertex coloring with $Δ+ 1$ colors such that no edge of $G$ is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time $O(nΔ)$. Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et. al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for $(ε+ 1)Δ$-coloring in the query model making $\tilde{O}(n\sqrt{n})$ queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of $Ω(n\sqrt n)$ for any $O(Δ)$-coloring is established on general graphs. In this work, we give a simple algorithm for $(1 + ε)Δ$-coloring. This algorithm makes $O(ε^{-1/2}n\sqrt{n})$ queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large $ε$. Additionally, it can be readily adapted to a quantum query algorithm making $\tilde{O}(ε^{-1}n^{4/3})$ queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of $Ω(n)$ for $O(Δ)$-coloring.