Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

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).