Applications of Gröbner Bases in Graph Coloring

This abstract has open access
Abstract Summary

Within this research, Computational Commutative Algebra was used to solve a common Graph Theory problem known as three colorability. A special kind of generator for the ideals of a polynomial ring in n-variables R[x1, x2, ... , xn] were studied. These generators are called Gröbner bases, which are suitable for solving many computational problems related to ideals of rings. Once a clear understanding of the derivation and properties of Gröbner bases was gained, the research focus shifted to applying them to the three colorability problem in graph theory. A map of the counties in Metropolitan Atlanta was chosen and calculations were performed to determine whether or not it was three colorable using Gröbner bases. To accomplish this, the map was reconstructed into a vertex graph with each county represented as a vertex and edges connecting the counties that shared a border. From there, the mathematics computer program Maple was used to compute the generators for the graph. The application of Gröbner bases go beyond coloring of graphs on a map. There are several other applications that are worth further research and exploration.

Abstract ID :
Submission Type
Abstract Topic

Associated Sessions