| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4653499 | European Journal of Combinatorics | 2014 | 14 Pages |
Abstract
By the Grünbaum–Aksenov Theorem (extending Grötzsch’s Theorem) every planar graph with at most three triangles is 33-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdős from 1990.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Oleg V. Borodin, Zdeněk Dvořák, Alexandr V. Kostochka, Bernard Lidický, Matthew Yancey,