Grobner Bases with Applications in Graph Theory

Thumbnail Image
Files
umi-umd-4013.pdf(193.11 KB)
No. of downloads: 3262
Publication or External Link
Date
2006-12-07
Authors
Hennessy, Angela
Advisor
Washington, Lawrence
Citation
DRUM DOI
Abstract
Grobner basis theory has been applied to the problem of graph coloring with novel results. A graph on n vertices is represented by a polynomial in n variables with degree equal to the number of edges in the graph. In the polynomial ring in n variables, the question of k-colorability is equivalent to determining if the polynomial which represents the graph is contained in a specific ideal. By finding a Grobner basis for this ideal, the problem becomes greatly simplified. We review two different approaches used to solve this problem, and demonstrate the techniques with examples. We also give an algebraic characterization of the Grobner basis of a particular ideal when there is a single k-coloring of a graph.
Notes
Rights