**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