Details:
Title | An algebraic characterization of uniquely vertex colorable graphs | Author(s) | Christopher Hillar, Troels Windfeldt | Type | Technical Report, Misc | Abstract | The 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. | Length | 12 |
File |
| Language | English | Year | 2006 | Translation |
No | Refereed |
No | Sponsors | RICAM, Special Semester on Groebner Bases 2006 |
|