Total coloring of planar graphs with 7-cycles containing at most two chords

被引：3

作者：

Xu, Renyu ^{[1
]}

Wu, Jian-Liang ^{[1
]}

机构：

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

来源：

THEORETICAL COMPUTER SCIENCE | 2014年 / 520卷

关键词：

Planar graph; Total coloring; Cycle; TOTAL CHROMATIC NUMBER;

D O I：

10.1016/j.tcs.2013.08.019

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A k-total-coloring of a graph G is a coloring of vertices and edges of G using k colors such that no two adjacent or incident elements receive the same color. In this paper, we prove that if G is a planar graph with maximum degree at least 8 and if every 7-cycle of G contains at most two chords, then G has a (Delta + 1)-total-coloring. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：124 / 129

页数：6

共 13 条

[1]

[Anonymous], 1968, USPEKHIMAT NAUK

[2]

Behzad M., 1965, Doctoral Thesis

[3]

Bondy A., 2008, GRAD TEXTS MATH, V244

[4]

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

[5] 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

[6] 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

[7] 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

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

Roussel, Nicolas ;

Zhu, Xuding .

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

[9]

Sanders DP, 1999, J GRAPH THEOR, V31, P67, DOI 10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO

[10]

2-C

← 1 2 →