Algebraic Characterization of Uniquely Vertex Colorable Graphs

Authors:
  • CHChristopher J. Hillar
    Christopher J. Hillar
  • TWTroels Windfeldt
    Troels Windfeldt

Abstract
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 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 the ideal $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.