Algorithms, Combinatorics and Optimization Seminar Carl Yerger
Davidson College
Title: Steinberg's Conjecture, the Bordeaux Coloring Conjecture and Near-Coloring

Abstract: An important result in the theory of graph coloring is Grotzsch's theorem, which states that every triangle-free planar graph is 3-colorable. A famous related question is due to Steinberg and states that any planar graph without 4- or 5-cycles is 3-colorable. In this talk, we will discuss some of the recent progress made towards proving Steinberg's conjecture and discuss joint work with Ken-ichi Kawarabayashi that planar graphs with no 5-cycles, 6-cycles or intersecting triangles are 3-colorable. In addition, we discuss recently completed senior thesis work based on near-coloring with Kyle Yang.

Date: Thursday, May 1, 2014
Time: 3:30 pm
Location:
Submitted by:  Boris Bukh