Algebraic Characterization of Uniquely Vertex Colorable Graphs

Details Algebraic Characterization of Uniquely Vertex Colorable Graphs Algebraic Characterization of Uniquely Vertex Colorable Graphs

2006-06-22

arxiv.org/abs/math/0606565v4

Mathematics

Combinatorics

15 pages, 2 figures, print version, to appear J. Comb. Th. Ser. B

Scientific paper

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 \in I_{G,k}$ for a certain ideal $I_{G,k} \subseteq \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.

Affiliated with

Also associated with

No associations

Rating

Algebraic Characterization of Uniquely Vertex Colorable Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algebraic Characterization of Uniquely Vertex Colorable Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic Characterization of Uniquely Vertex Colorable Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-208657