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 :
2018-8333
Submission Type
Abstract Topic

Associated Sessions

Spelman College

Abstracts With Same Type

Abstract ID
Abstract Title
Abstract Topic
Submission Type
Primary Author
2018-38194
History
Oral
Ashley Borneo
2018-59275
Political Science
Oral
Janeal Hightower Fordham
2018-21200
History
Oral
Tamia DeBarros-Cannon
2018-45282
English
Oral
Angelica Johnson
2018-67281
English
Oral
Jordan Branch
109 visits