Portal de Periódicos da CAPES

Short proofs of coloring theorems on planar graphs

2013; Elsevier BV; Volume: 36; Linguagem: Inglês

10.1016/j.ejc.2013.05.002

1095-9971

O. V. Borodin, Alexandr Kostochka, Bernard Lidický, Matthew Yancey,

Limits and Structures in Graph Theory

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\"otzsch 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\"unbaum-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.