  The study of graph vertex colorability from an algebraic perspective has
introduced novel techniques and algorithms into the field. For instance, it is
known that $k$-colorability of a graph $G$ is equivalent to the condition $1
\in I_{G,k}$ for a certain ideal $I_{G,k} \subseteq \k[x_1, ..., x_n]$. In this
paper, we extend this result by proving a general decomposition theorem for
$I_{G,k}$. This theorem allows us to give an algebraic characterization of
uniquely $k$-colorable graphs. Our results also give algorithms for testing
unique colorability. As an application, we verify a counterexample to a
conjecture of Xu concerning uniquely 3-colorable graphs without triangles.
