Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Algebraic Characterization of Uniquely Colorizable GraphsAlgebra & 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).