Short proofs of coloring theorems on planar graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-11
Main Authors: Borodin, Oleg V, Kostochka, Alexandr V, Lidický, Bernard, Yancey, Matthew
Format: Article
Language:English
Subjects:
Coloring
Graph theory
Graphs
Lower bounds
Theorems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1211.3981