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…
Contents
1 Introduction
2 Gr¨obner Bases
3 Graph Coloring
3.1 Examples
3.2 Uniquely Colorable Graphs
4 Another Approach to Graph Coloring
4.1 Bipartite Graphs
4.2 Graph Coloring with Roots of Unity
4.3 Enumeration of Graph Colorings
Author: Hennessy, Angela
Source: University of Maryland
Download URL 2: Visit Now