An Exploration of Algebraic Approaches to Graph Theory
Date
2016-05-31
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
graph theory, commutative algebra, nullstellensatz, graph coloring, hamiltonian graphs