![](https://d3ilqtpdwi981i.cloudfront.net/sB7PTSHq_t1dZnGC5hLTYbe3mXs=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/5e/51/b9/5e51b944-3433-464f-b61d-023b31d9a533/thumbnail_017e4662-8354-4c01-8160-4b637ecaa4cf.jpg)
Article
Short proofs of coloring theorems on planar graphs
European Journal of Combinatorics
(2014)
Abstract
A lower bound on the number of edges in a -critical -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 -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 -colorable.
Disciplines
Publication Date
February, 2014
DOI
10.1016/j.ejc.2013.05.002
Publisher Statement
This is a manuscript of an article published as Borodin, Oleg V., Alexandr V. Kostochka, Bernard Lidický, and Matthew Yancey. "Short proofs of coloring theorems on planar graphs." European Journal of Combinatorics 36 (2014): 314-321. doi:10.1016/j.ejc.2013.05.002. Copyright 2014 Elsevier Ltd. Posted with permission.
Citation Information
Oleg V. Borodin, Alexandr V. Kostochka, Bernard Lidicky and Matthew Yancey. "Short proofs of coloring theorems on planar graphs" European Journal of Combinatorics Vol. 36 (2014) p. 314 - 321 Available at: http://works.bepress.com/bernard-lidicky/15/