An 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, $k$-colorability of a graph can be characterized in terms of whether its graph polynomial is contained in a certain ideal. In this paper, we interpret unique colorability in an analogous manner and prove an algebraic characterization for uniquely $k$-colorable graphs. Our result also gives algorithms for testing unique colorability. As an application, we verify a counterexample to a conjecture of Xu concerning uniquely 3-colorable graphs without triangles.