Algebraic Characterization of Uniquely Vertex Colorable Graphs
Authors:
- Christopher J. HillarCHChristopher J. Hillar
- Troels WindfeldtTWTroels Windfeldt
Preprint
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.