Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Algebraic Characterization of Uniquely Colorizable Graphs

Algebra & Discrete Mathematics

Speaker: Chris Hillar, Texas A & M
Location: 1147 MSB
Start time: Fri, Mar 2 2007, 1:10PM

The study of graph 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 talk, we interpret unique colorability in an analogous manner and use Groebner basis techniques to 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. (Joint with Troels Windfeldt).