Grobner Bases with Applications in Graph Theory

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…


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

Leave a Comment