Planar 4-critical graphs with four triangles

被引：13

作者：

Borodin, Oleg V. ^{[1
,2
]}

Dvorak, Zdenek ^{[3
]}

Kostochka, Alexandr V. ^{[1
,4
]}

Lidicky, Bernard ^{[4
]}

Yancey, Matthew ^{[4
]}

机构：

[1] Sobolev Inst Math, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, Novosibirsk 630090, Russia

[3] Charles Univ Prague, Inst Comp Sci, Prague, Czech Republic

[4] Univ Illinois, Urbana, IL 61801 USA

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2014年 / 41卷

基金：

俄罗斯基础研究基金会; 美国国家科学基金会;

关键词：

D O I：

10.1016/j.ejc.2014.03.009

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2014 Elsevier Ltd. All rights reserved.

引用

页码：138 / 151

页数：14

共 26 条

[1] Aksenov V.A., 1974, DROP
[2] Aksenov V.A., 2004, SIB ELEKT MAT IZV, V1, P117
[3] Aksenov V.A., 2003, REF MISMAT, V110, P3
[4] Aksenov V.A., 1974, GRAFY TESTY, P3
[5] Aksionov V., 1978, COMBIN C MATH SOC J, V18, P23
[6] SOME COUNTEREXAMPLES ASSOCIATED WITH THE 3-COLOR PROBLEM
AKSIONOV, VA
MELNIKOV, LS
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (01) : 1 - 9
[7] Colorings of plane graphs: A survey
Borodin, O. V.
[J]. DISCRETE MATHEMATICS, 2013, 313 (04) : 517 - 539
[8] A new proof of Grunbaum's 3 color theorem
Borodin, OV
[J]. DISCRETE MATHEMATICS, 1997, 169 (1-3) : 177 - 183
[9] Dirac G. A., 1964, J. Reine Angew. Math (Crelles J.), V1964, P43
[10] Dirac GA., 1953, FUND MATH, V40, P42

← 1 2 3 →