Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleAn algebraic characterization of uniquely vertex colorable graphs
Author(s) Christopher Hillar, Troels Windfeldt
TypeTechnical Report, Misc
AbstractThe 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.
Translation No
Refereed No
SponsorsRICAM, Special Semester on Groebner Bases 2006