Short proofs of coloring theorems on planar graphs

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

Research output: Contribution to journalArticlepeer-review

Abstract

A lower bound on the number of edges in a k-critical n-vertex graph recently obtained 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 which is the Grünbaum-Aksenov Theorem that every planar graph 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 4 is 3-colorable.

Original languageEnglish (US)
Pages (from-to)314-321
Number of pages8
JournalEuropean Journal of Combinatorics
Volume36
DOIs
StatePublished - Feb 2014

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Short proofs of coloring theorems on planar graphs'. Together they form a unique fingerprint.

Cite this