Acyclic edge coloring of planar graphs with girth at least 5

被引：7

作者：

Hou, Jianfeng ^{[1
]}

Wang, Weitao ^{[1
]}

Zhang, Xiaoran ^{[1
]}

机构：

[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 18期

基金：

中国国家自然科学基金;

关键词：

Planar graph; Girth; Acyclic edge coloring; Critical; SPARSE HESSIAN MATRICES; CHROMATIC INDEXES;

D O I：

10.1016/j.dam.2013.06.013

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A proper edge coloring of a graph G is acyclic if there is no bichromatic cycle in G. The acyclic chromatic index of G, denoted chi(a)'(G), is the least number of colors k such that G has an acyclic k-edge-coloring. In this paper, it is shown that if G is a planar graph with girth at least 5 and maximum degree Delta, then chi(a)'(G) <= Delta + 1. Moreover, Delta >= 9, then chi(a)'(G) = Delta. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：2958 / 2967

页数：10

共 23 条

[21] Acyclic edge coloring of planar graphs without 5-cycles [J].

Shu, Qiaojun ;

Wang, Weifan ;

Wang, Yiqiao .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) :1211-1223

[22] Acyclic chromatic indices of planar graphs with large girth [J].

Wang, Weifan ;

Shu, Qiaojun ;

Wang, Kan ;

Wang, Ping .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) :1239-1253

[23] Acyclic edge coloring of planar graphs with large girth [J].

Yu, Dongxiao ;

Hou, Jianfeng ;

Liu, Guizhen ;

Liu, Bin ;

Xu, Lan .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (47-49) :5196-5200

← 1 2 3 →