Total coloring of embedded graphs of maximum degree at least ten

被引：3

作者：

Hou JianFeng ^{[1
,2
]}

Wu JianLiang ^{[1
]}

Liu GuiZhen ^{[1
]}

Liu Bin ^{[1
]}

机构：

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

[2] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Peoples R China

来源：

SCIENCE CHINA-MATHEMATICS | 2010年 / 53卷 / 08期

基金：

中国国家自然科学基金;

关键词：

surface; Euler characteristic; total coloring; total chromatic number; TOTAL CHROMATIC NUMBER; LIST-TOTAL COLORINGS; PLANAR GRAPHS; SURFACES; EDGE;

D O I：

10.1007/s11425-010-3089-5

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A total k-coloring of a graph G is a coloring of V (G) boolean OR E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number chi ''(G) is the smallest integer k such that G has a total k-coloring. In this paper, it is proved that the total chromatic number of any graph G embedded in a surface Sigma of Euler characteristic chi(Sigma) >= 0 is Delta(G) + 1 if Delta >= 10, where Delta(G) denotes the maximum degree of G.

引用

页码：2127 / 2133

页数：7

共 21 条

[1]

[Anonymous], 1968, USPEKHIMAT NAUK

[2]

Behzad M., 1965, Doctoral Thesis

[3]

Borodin OV, 1997, J GRAPH THEOR, V26, P53, DOI 10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO

[4]

2-G

[5] Total colourings of planar graphs with large girth [J].

Borodin, OV ;

Kostochka, AV ;

Woodall, DR .

EUROPEAN JOURNAL OF COMBINATORICS, 1998, 19 (01) :19-24

[6]

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

[7] Total colorings of planar graphs without small cycles [J].

Hou, Jianfeng ;

Zhu, Yan ;

Liu, Guizhen ;

Wu, Jianliang ;

Lan, Mei .

GRAPHS AND COMBINATORICS, 2008, 24 (02) :91-100

[8] List edge and list total colorings of planar graphs without 4-cycles [J].

Hou, Jianfeng ;

Liu, Guizhen ;

Cai, Jiansheng .

THEORETICAL COMPUTER SCIENCE, 2006, 369 (1-3) :250-255

[9]

Kostochka A. V., 1978, Ph.D. Thesis

[10] TOTAL COLORING OF A MULTI-GRAPH WITH MAXIMAL DEGREE-4 [J].

KOSTOCHKA, AV .

DISCRETE MATHEMATICS, 1977, 17 (02) :161-163

← 1 2 3 →