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 条

[1] Acyclic edge colorings of graphs [J].

Alon, N ;

Sudakov, B ;

Zaks, A .

JOURNAL OF GRAPH THEORY, 2001, 37 (03) :157-167

[2] A PARALLEL ALGORITHMIC VERSION OF THE LOCAL LEMMA [J].

ALON, N .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :367-378

[3] Optimal acyclic edge-coloring of cubic graphs [J].

Andersen, Lars Dovling ;

Macajova, Edita ;

Mazak, Jan .

JOURNAL OF GRAPH THEORY, 2012, 71 (04) :353-364

[4]

Basavaraju M., 2010, DISCRETE MATH, V310, P1445

[5] ACYCLIC EDGE-COLORING OF PLANAR GRAPHS [J].

Basavaraju, Manu ;

Chandran, L. Sunil ;

Cohen, Nathann ;

Havet, Frederic ;

Mueller, Tobias .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) :463-478

[6] Acyclic Edge Coloring of Graphs with Maximum Degree 4 [J].

Basavaraju, Manu ;

Chandran, L. Sunill .

JOURNAL OF GRAPH THEORY, 2009, 61 (03) :192-209

[7] ESTIMATION OF SPARSE HESSIAN MATRICES AND GRAPH-COLORING PROBLEMS [J].

COLEMAN, TF ;

MORE, JJ .

MATHEMATICAL PROGRAMMING, 1984, 28 (03) :243-270

[8] THE CYCLIC COLORING PROBLEM AND ESTIMATION OF SPARSE HESSIAN MATRICES [J].

COLEMAN, TF ;

CAI, JY .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02) :221-235

[9] Some results on acyclic edge coloring of plane graphs [J].

Dong, Wei ;

Xu, Baogang .

INFORMATION PROCESSING LETTERS, 2010, 110 (20) :887-892

[10] Star coloring of graphs [J].

Fertin, G ;

Raspaud, A ;

Reed, B .

JOURNAL OF GRAPH THEORY, 2004, 47 (03) :163-182

← 1 2 3 →