Title: An algorithm to determine the 3-colorabilty of graphs with minimum degree at least 6
Speaker: Nicholas Crawford, University of Colorado Denver

Abstract:
Graph coloring started as a formal problem back in the 1850’s when Augustus De Morgan sent a letter to William Rowan Hamilton asking about the now famous 4-coloring problem. Proper vertex coloring, the coloring of vertices in which no two adjacent vertices receive the same color, is a category of graph theory that has many applications in computer science and engineering. The fastest known algorithm determining if a general graph is 3-colorable was proved by Beigal and Eppstein in 2013. In this presentation we will explore the subset of graphs in which the minimum degree is bounded and find a new algorithm which improves on Beigel and Eppstein's for this specific class of graphs.

The proof of this algorithm relies on 3 cases based on the degree of a particular vertex. In one case we rely on Boolean Algebra techniques in order to transfer the graph into a satisfiability problem. The satisfiability problems determine whether given an set of variables and constraints the overall statement is true. There is a natural correspondence between 3-SAT problems and the 3-coloring problem.