Algebraic Characterization of Uniquely Colorizable GraphsAlgebra & Discrete Mathematics
|Speaker:||Chris Hillar, Texas A & M|
|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).