Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleAlgebraic characterization of uniquely vertex colorable graphs
Author(s) Christopher Hillar, Troels Windfeldt
TypeArticle in Journal
AbstractThe study of graph vertex colorability from an algebraic perspective has introduced novel techniques and algorithms into the field. For instance, it is known that k-colorability of a graph G is equivalent to the condition 1 ∈ I G , k for a certain ideal I G , k ⊆ k [ x 1 , , x n ] . In this paper, we extend this result by proving a general decomposition theorem for I G , k . This theorem allows us to give an algebraic characterization of uniquely k-colorable graphs. Our results also give algorithms for testing unique colorability. As an application, we verify a counterexample to a conjecture of Xu concerning uniquely 3-colorable graphs without triangles.
KeywordsVertex coloring, Gröbner basis, Colorability algorithm, Uniquely colorable graph
ISSN0095-8956
URL http://www.sciencedirect.com/science/article/pii/S009589560700086X
LanguageEnglish
JournalJournal of Combinatorial Theory, Series B
Volume98
Number2
Pages400 - 414
Year2008
Edition0
Translation No
Refereed No
Webmaster