Planar graphs without 4-cycles and close triangles are (2,0,0)-colorable

被引：1

作者：

Hoskins, Heather ^{[1
]}

Liu, Runrun ^{[2
]}

Vandenbussche, Jennifer ^{[3
]}

Yu, Gexin ^{[1
,2
]}

机构：

[1] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA

[2] Cent China Normal Univ, Dept Math & Stat, Wuhan, Hubei, Peoples R China

[3] Kennesaw State Univ, Dept Math, Marietta, GA 30060 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2018年 / 36卷 / 02期

关键词：

Planar graphs; 3-Colorable; Discharging; STEINBERGS CONJECTURE; LENGTH; 4; CYCLES; RELAXATION; MAP;

D O I：

10.1007/s10878-018-0298-2

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

For a set of nonnegative integers , a -coloring of a graph G is a partition of V(G) into such that for every i, has maximum degree at most . We prove that all planar graphs without 4-cycles and no less than two edges between triangles are (2, 0, 0)-colorable.

引用

页码：346 / 364

页数：19

共 20 条

[1] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING
APPEL, K
HAKEN, W
[J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 429 - 490
[2] EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY
APPEL, K
HAKEN, W
KOCH, J
[J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 491 - 567
[3] Vertex Decompositions of Sparse Graphs into an Edgeless Subgraph and a Subgraph of Maximum Degree at Most k
Borodin, O. V.
Ivanova, A. O.
Montassier, M.
Ochem, P.
Raspaud, A.
[J]. JOURNAL OF GRAPH THEORY, 2010, 65 (02) : 83 - 93
[4] Planar graphs without cycles of length from 4 to 7 are 3-colorable
Borodin, OV
Glebov, AN
Raspaud, A
Salavatipour, MR
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 93 (02) : 303 - 311
[5] Planar graphs without cycles of length 4 or 5 are (2,0,0)-colorable
Chen, Ming
Wang, Yingqian
Liu, Peipei
Xu, Jinghan
[J]. DISCRETE MATHEMATICS, 2016, 339 (02) : 886 - 905
[6] Steinberg's Conjecture is false
Cohen-Addad, Vincent
Hebdige, Michael
Kral, Daniel
Li, Zhentao
Salgado, Esteban
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 452 - 456
[7] DEFECTIVE COLORINGS OF GRAPHS IN SURFACES - PARTITIONS INTO SUBGRAPHS OF BOUNDED VALENCY
COWEN, LJ
COWEN, RH
WOODALL, DR
[J]. JOURNAL OF GRAPH THEORY, 1986, 10 (02) : 187 - 195
[8] Dvorak Z., 2009, ARXIV09110885
[9] Grotzch H, 1958, WISS Z MARTIN LUTHER, P109
[10] Havel I., 1969, J COMB THEORY B, V7, P184

← 1 2 →