Algebraic Characterization of Uniquely Vertex Colorable Graphs
| dc.creator | Hillar, Christopher J. | |
| dc.creator | Windfeldt, Troels | |
| dc.date | 2006-06-22 | |
| dc.date | 2007-09-24 | |
| dc.date.accessioned | 2026-07-07T08:31:36Z | |
| dc.date.available | 2026-07-07T08:31:36Z | |
| dc.description | 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. | |
| dc.description | 15 pages, 2 figures, print version, to appear J. Comb. Th. Ser. B | |
| dc.identifier | https://arxiv.org/abs/math/0606565 | |
| dc.identifier | http://arxiv.org/abs/math/0606565 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/138546 | |
| dc.subject | Combinatorics | |
| dc.subject | Commutative Algebra | |
| dc.title | Algebraic Characterization of Uniquely Vertex Colorable Graphs | |
| dc.type | text |