An Exploration of Algebraic Approaches to Graph Theory
MetadataShow full item record
In a 2010 paper, De Loera et al. explore the use of polynomial ideals to determine properties of graphs. Here we present an exposition of the results in said paper on k-colorability and Hamiltonicity of graphs, as well as the improvements on these results made by Li et al. in 2015. We provide detail and background necessary for an undergraduate reader. Additionally, we provide an explicit formula for the Nullstellensatz certificate of non-2-colorability of a graph, and find the graph with smallest order that has a linear Nullstellensatz certificate of non-3-colorability but does not contain an odd wheel.