Charles Explorer logo
🇨🇿

Planar 4-critical graphs with four triangles

Publikace na Matematicko-fyzikální fakulta |
2014

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

By the Grunbaum-Aksenov Theorem (extending Grotzsch's Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles.

We describe all such graphs. This answers a question of Erdos from 1990.