The ACO Seminar (2013–2014)

An important result in the theory of graph coloring is Grötzsch'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.