Many 3-colorings of triangle-free planar graphs

被引：19

作者：

Thomassen, Carsten ^{[1
]}

机构：

[1] Tech Univ Denmark, Dept Math, DK-2800 Lyngby, Denmark

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2007年 / 97卷 / 03期

关键词：

planar graphs; many; 3-colorings;

D O I：

10.1016/j.jctb.2006.06.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Grotzsch proved that every planar triangle-free graph is 3-colorable. We prove that it has at least 2(n1/2)/20000 distinct 3-colorings where n is the number of vertices. If the graph has girth at least 5, then it has at least 2(n/10000) distinct list-colorings provided every vertex has at least three available colors. (c) 2006 Elsevier Inc. All rights reserved.

引用

页码：334 / 349

页数：16

共 17 条

[1]

[Anonymous], GRAPHS SURFACES

[2]

Bondy J.A., 2008, GRAD TEXTS MATH

[3] Coloring graphs with fixed genus and girth [J].

Gimbel, J ;

Thomassen, C .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1997, 349 (11) :4555-4564

[4]

Grotzsch H., 1959, Halle-Wittenberg Math.-Natur. Reihe, V8, P109

[5]

Jensen TR, 2000, J GRAPH THEOR, V34, P234, DOI 10.1002/1097-0118(200007)34:3<234::AID-JGT4>3.0.CO

[6]

2-G

[7]

KOWALIK L, UNPUB FAST 3 COLORIN

[8]

STEINBERG R, 1989, ARS COMBINATORIA, V28, P15

[9] EVERY PLANAR GRAPH IS 5-CHOOSABLE [J].

THOMASSEN, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) :180-181

[10] A short list color proof of Grotzsch's theorem [J].

Thomassen, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (01) :189-192

← 1 2 →