Planar graphs without intersecting 5-cycles are 4-choosable

被引：9

作者：

Hu, Dai-Qiang ^{[1
]}

Wu, Jian-Liang ^{[2
]}

机构：

[1] Jinan Univ, Dept Math, Guangzhou 510632, Guangdong, Peoples R China

[2] Shandong Univ, Sch Math, Jinan 250100, Peoples R China

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 08期

关键词：

planar graph; Cycle; List coloring; Choosable; EDGE CHOOSABILITY; TRIANGLES; COLORINGS; 4-CYCLES; CYCLES;

D O I：

10.1016/j.disc.2017.03.012

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G is k-choosable if it can be properly colored whenever every vertex has a list of at least k available colors. In the paper, it is proved that all planar graphs without intersecting 5-cycles are 4-choosable. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：1788 / 1792

页数：5

共 14 条

[1] COLORINGS AND ORIENTATIONS OF GRAPHS [J].

ALON, N ;

TARSI, M .

COMBINATORICA, 1992, 12 (02) :125-134

[2]

Bondy J., 2008, GRADUATE TEXTS MATH

[3] Planar graphs without 4-cycles adjacent to triangles are 4-choosable [J].

Cheng, Panpan ;

Chen, Min ;

Wang, Yingqian .

DISCRETE MATHEMATICS, 2016, 339 (12) :3052-3057

[4]

Erdos P., 1979, C NUMERANTUM, V26, P125

[5] PLANAR GRAPHS WITHOUT 7-CYCLES ARE 4-CHOOSABLE [J].

Farzad, Babak .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) :1179-1199

[6] Planar graphs without cycles of specific lengths [J].

Fijavz, G ;

Juvan, M ;

Mohar, B ;

Skrekovski, R .

EUROPEAN JOURNAL OF COMBINATORICS, 2002, 23 (04) :377-388

[7]

Lam PCB, 1999, J COMB THEORY B, V76, P117

[8] On structure of some plane graphs with application to choosability [J].

Lam, PCB ;

Shiu, WC ;

Xu, BG .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 82 (02) :285-296

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

THOMASSEN, C .

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

[10]

Vizing V.G., 1976, Metody Diskret. Analiz, V29, P3

← 1 2 →