Total Coloring of Planar Graphs Without Chordal Short Cycles

被引：5

作者：

Wang, Huijuan ^{[1
]}

Liu, Bin ^{[2
]}

Wu, Jianliang ^{[3
]}

机构：

[1] Qingdao Univ, Coll Math, Qingdao 266071, Peoples R China

[2] Ocean Univ China, Dept Math, Qingdao 266100, Peoples R China

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

来源：

GRAPHS AND COMBINATORICS | 2015年 / 31卷 / 05期

基金：

中国国家自然科学基金;

关键词：

Planar graph; Total coloring; Cycle; TOTAL CHROMATIC NUMBER; MAXIMUM DEGREE 8; TRIANGLES; SURFACES;

D O I：

10.1007/s00373-014-1449-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let be a planar graph with and be a vertex of . It is proved that if is not incident with chordal - or -cycles by Shen et al. (Appl Math Lett 22:1369-1373, 2009), or is not incident with -chordal -cycle by Chang et al. (Theor Comput Sci 476:16-23, 2013). In this paper we generalize these results and prove that if is not incident with chordal -cycle, or chordal -cycle, or -chordal -cycle, then .

引用

页码：1755 / 1764

页数：10

共 20 条

[1]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[2]

BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180

[3] Local condition for planar graphs of maximum degree 7 to be 8-totally colorable [J].

Chang, Gerard Jennhwa ;

Hou, Jianfeng ;

Roussel, Nicolas .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (08) :760-768

[4] Total colorings of planar graphs with maximum degree 8 and without 5-cycles with two chords [J].

Chang, Jian ;

Wang, Hui-Juan ;

Wu, Jian-Liang ;

A, Yong-Ga .

THEORETICAL COMPUTER SCIENCE, 2013, 476 :16-23

[5] Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable [J].

Du, Dingzhu ;

Shen, Lan ;

Wang, Yingqian .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (13) :2778-2784

[6] Total coloring of planar graphs without 6-cycles [J].

Hou, Jianfeng ;

Liu, Bin ;

Liu, Guizhen ;

Wu, Jianliang .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (2-3) :157-163

[7] The total chromatic number of any multigraph with maximum degree five is at most seven [J].

Kostochka, AV .

DISCRETE MATHEMATICS, 1996, 162 (1-3) :199-214

[8] TOTAL-COLORING OF PLANE GRAPHS WITH MAXIMUM DEGREE NINE [J].

Kowalik, Lukasz ;

Sereni, Jean-Sebastien ;

Skrekovski, Riste .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) :1462-1479

[9] Total colorings and list total colorings of planar graphs without intersecting 4-cycles [J].

Liu, Bin ;

Hou, Jianfeng ;

Wu, Jianliang ;

Liu, Guizhen .

DISCRETE MATHEMATICS, 2009, 309 (20) :6035-6043

[10] Total coloring of planar graphs of maximum degree eight [J].

Roussel, Nicolas ;

Zhu, Xuding .

INFORMATION PROCESSING LETTERS, 2010, 110 (8-9) :321-324

← 1 2 →