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.

The Cycle Double Cover Problem in Graph Theory suggests that all 2-connected graphs share a certain property with 2-connected planar maps. Such a map clearly contains a collection of cycles, indeed the boundary cycles of its faces, such that each edge belongs to exactly
two of them. The generalization of this property to nonplanar graphs remains one of the central open problems in Graph Theory.

We investigate this problem by generalizing a suitable variation of the statement of another almost obvious property of planar maps, namely the Jordan Curve Theorem. The generalization suggests a new conjecture which is much stronger than the Cycle Double Cover Conjecture. In fact it would imply a very strong form of the Cycle Double Cover Conjecture, suggesting that every cycle in a 2-connected graph appears in at least one cycle double cover of the graph.

We prove the stronger conjecture in a few important special cases.