@article{db8ad9bb1d7b4feab0f035fe436b387d,
title = "Planar 4-critical graphs with four triangles",
abstract = "By the Gr{\"u}nbaum-Aksenov Theorem (extending Gr{\"o}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.",
author = "Borodin, {Oleg V.} and Zden{\v e}k Dvo{\v r}{\'a}k and Kostochka, {Alexandr V.} and Bernard Lidick{\'y} and Matthew Yancey",
note = "Funding Information: The first author{\textquoteright}s research is supported in part by grants 12-01-0044 and 12-01-00631 of the Russian Foundation for Basic Research and by Grant NSh-1939.2014.1 of the President of Russia for Leading Scientific Schools . The second author is supported by the Center of Excellence—Inst. for Theor. Comp. Sci., Prague (project P202/12/G061 of Czech Science Foundation), and by project LH12095 (New combinatorial algorithms—decompositions, parameterization, efficient solutions) of Czech Ministry of Education. The third author is supported by NSF grant DMS-0965587 and NSF grants DMS-1266016 . The fourth author is supported by NSF grants DMS-1266016 . The fifth author{\textquoteright}s research is supported by National Science Foundation grant DMS 08-38434 “EMSW21-MCTP: Research Experience for Graduate Students”.",
year = "2014",
month = oct,
doi = "10.1016/j.ejc.2014.03.009",
language = "English (US)",
volume = "41",
pages = "138--151",
journal = "European Journal of Combinatorics",
issn = "0195-6698",
publisher = "Academic Press Inc.",
}