Grobner Bases with Applications in Graph Theory

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.