Planar 4-critical graphs with four triangles

Abstract

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.

20 pages, 7 figures

References in corpus (2)

• 3-coloring triangle-free planar graphs with a precolored 8-cycle
• 3-coloring triangle-free planar graphs with a precolored 9-cycle

Cited by in corpus (8)

• Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles
• Fine structure of 4-critical triangle-free graphs III. General surfaces
• 3-coloring triangle-free planar graphs with a precolored 9-cycle
• Maximal distance spectral radius of 4-chromatic planar graphs
• Fine structure of 4-critical triangle-free graphs I. Planar graphs with two triangles and 3-colorability of chains
• Spanning Triangle-trees and Flows of Graphs
• Further Extensions of the Grötzsch Theorem
• Some New Methods for Constructing 4-critical Planar Graphs