Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653612 | European Journal of Combinatorics | 2014 | 8 Pages |
Abstract
A lower bound on the number of edges in a kk-critical nn-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 33-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 33-colorable.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Oleg V. Borodin, Alexandr V. Kostochka, Bernard Lidický, Matthew Yancey,