Skip to main content
Article
Short proofs of coloring theorems on planar graphs
European Journal of Combinatorics (2014)
  • Oleg V. Borodin, Sobolev Institute of Mathematics
  • Alexandr V. Kostochka, University of Illinois at Urbana-Champaign
  • Bernard Lidicky, University of Illinois at Urbana-Champaign
  • Matthew Yancey, University of Illinois at Urbana-Champaign
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.
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/