Planar 4-critical graphs with four triangles

Oleg V. Borodin, Zdeněk Dvořák, Alexandr V. Kostochka, Bernard Lidický, Matthew Yancey

Research output: Contribution to journalArticlepeer-review

Abstract

By the Grünbaum-Aksenov Theorem (extending Grötzsch'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.

Original languageEnglish (US)
Pages (from-to)138-151
Number of pages14
JournalEuropean Journal of Combinatorics
Volume41
DOIs
StatePublished - Oct 2014

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Planar 4-critical graphs with four triangles'. Together they form a unique fingerprint.

Cite this