Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

Planar 4-critical graphs with four triangles

2014; Elsevier BV; Volume: 41; Linguagem: Inglês

10.1016/j.ejc.2014.03.009

ISSN

1095-9971

Autores

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

Tópico(s)

Limits and Structures in Graph Theory

Resumo

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.

Referência(s)