KAIST Discrete Math Seminar

The fundamental sufficient condition for the existence of a proper 3-coloring of the vertices of a planar graph G was proved by Grötzsch more than 50 years ago, and it requires that G has no triangles (cycles of length 3). This talk discusses conjectures for other possible sufficient conditions, some of which have stubbornly resisted proofs for decades, and also various recent partial results. A conjecture in a different direction deals with a stronger 3-colorability property, which for a planar graph turns out to be equivalent to triangle-freeness, but here it is unknown whether the assumption of planarity may be weakened.