Details:
Title  Algebraic characterization of uniquely vertex colorable graphs  Author(s)  Christopher Hillar, Troels Windfeldt  Type  Article in Journal  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 kcolorability of a graph G is equivalent to the condition 1 ∈ I G , k for a certain ideal I G , k ⊆ 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 kcolorable graphs. Our results also give algorithms for testing unique colorability. As an application, we verify a counterexample to a conjecture of Xu concerning uniquely 3colorable graphs without triangles.  Keywords  Vertex coloring, Gröbner basis, Colorability algorithm, Uniquely colorable graph  ISSN  00958956 
URL 
http://www.sciencedirect.com/science/article/pii/S009589560700086X 
Language  English  Journal  Journal of Combinatorial Theory, Series B  Volume  98  Number  2  Pages  400  414  Year  2008  Edition  0  Translation 
No  Refereed 
No 
