Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B
Volume 98, Issue 2, Pages 400-414Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2007.08.004
Keywords
vertex coloring; Grobner basis; colorability algorithm; uniquely colorable graph
Categories
Ask authors/readers for more resources
The 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 is an element of I-G,I-k for a certain ideal I-G,I-k subset of k[x(1),..., x(n)]. In this paper, we extend this result by proving a general decomposition theorem for I-G,I-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. (C) 2007 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available