  The fastest known classical algorithm deciding the $k$-colorability of
$n$-vertex graph requires running time $\Omega(2^n)$ for $k\ge 5$. In this
work, we present an exponential-space quantum algorithm computing the chromatic
number with running time $O(1.9140^n)$ using quantum random access memory
(QRAM). Our approach is based on Ambainis et al's quantum dynamic programming
with applications of Grover's search to branching algorithms. We also present a
polynomial-space quantum algorithm not using QRAM for the graph $20$-coloring
problem with running time $O(1.9575^n)$. In the polynomial-space quantum
algorithm, we essentially show $(4-\epsilon)^n$-time classical algorithms that
can be improved quadratically by Grover's search.
