  Given a graph $G$ with $n$ vertices and maximum degree $\Delta$, it is known
that $G$ admits a vertex coloring with $\Delta + 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\Delta)$.
  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
$(\epsilon + 1)\Delta$-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 $\Omega(n\sqrt n)$ for any
$O(\Delta)$-coloring is established on general graphs.
  In this work, we give a simple algorithm for $(1 + \epsilon)\Delta$-coloring.
This algorithm makes $O(\epsilon^{-1/2}n\sqrt{n})$ queries, which matches the
best existing algorithms as well as the classical lower bound for sufficiently
large $\epsilon$. Additionally, it can be readily adapted to a quantum query
algorithm making $\tilde{O}(\epsilon^{-1}n^{4/3})$ queries, bypassing the
classical lower bound. Complementary to these algorithmic results, we show a
quantum lower bound of $\Omega(n)$ for $O(\Delta)$-coloring.
