Short proofs of coloring theorems on planar graphs

Abstract

A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grötzsch Theorem that every planar triangle-free graph is 3-colorable. In this paper we use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Grünbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most four is 3-colorable.

13 pages, 4 figures

References in corpus (1)

• Ore's Conjecture for $k=4$ and Gr\" otzsch Theorem

Cited by in corpus (7)

• 3-coloring triangle-free planar graphs with a precolored 8-cycle
• 4-critical graphs on surfaces without contractible (<=4)-cycles
• 3-coloring triangle-free planar graphs with a precolored 9-cycle
• Note on 3-Choosability of Planar Graphs with Maximum Degree 4
• Further Extensions of the Grötzsch Theorem
• Sparse $4$-critical graphs have low circular chromatic number
• On the Minimum Edge-Density of 4-Critical Graphs of Girth Five