Details:

Title	An algebraic characterization of uniquely vertex colorable graphs
Author(s)	Christopher Hillar, Troels Windfeldt
Type	Technical Report, Misc
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.
Length	12
File
Language	English
Year	2006
Translation	No
Refereed	No
Sponsors	RICAM, Special Semester on Groebner Bases 2006