Planar 4-critical graphs with four triangles

Alexandr V. Kostochka; Bernard Lidick\'y; Matthew Yancey; Oleg V. Borodin; Zden\v{e}k Dvo\v{r}\'ak

arxiv: 1306.1477 · v1 · pith:PEEVL4NWnew · submitted 2013-06-06 · 🧮 math.CO · cs.DM

Planar 4-critical graphs with four triangles

Oleg V. Borodin , Zden\v{e}k Dvo\v{r}\'ak , Alexandr V. Kostochka , Bernard Lidick\'y , Matthew Yancey This is my paper

classification 🧮 math.CO cs.DM

keywords graphsplanartrianglescriticalfourtheoremanswerscolorable

0 comments

read the original 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.

This paper has not been read by Pith yet.

Planar 4-critical graphs with four triangles

discussion (0)