Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

被引：20

作者：

Shu, Qiaojun ^{[1
]}

Wang, Weifan ^{[1
]}

Wang, Yiqiao ^{[2
]}

机构：

[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

[2] Beijing Univ Chinese Med, Sch Hlth Management, Beijing 100029, Peoples R China

来源：

JOURNAL OF GRAPH THEORY | 2013年 / 73卷 / 04期

关键词：

acyclic edge coloring; planar graph; girth; maximum degree; EDGE COLORINGS;

D O I：

10.1002/jgt.21683

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamcik (Math. Slovaca 28 (1978), 139-145) and later Alon et al. (J Graph Theory 37 (2001), 157-167) conjectured that a(G)+2 for any simple graph G with maximum degree . In this article, we confirm this conjecture for planar graphs of girth at least 4. (C) 2012 Wiley Periodicals, Inc.

引用

页码：386 / 399

页数：14

共 20 条

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

Alon, N ;

Sudakov, B ;

Zaks, A .

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

[2] ACYCLIC COLORING OF GRAPHS [J].

ALON, N ;

MCDIARMID, C ;

REED, B .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :277-288

[3]

Basavaraju M., ACYCLIC EDGE COLORIN

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

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

Basavaraju, Manu ;

Chandran, L. Sunill .

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

[6] Acyclic edge colouring of planar graphs without short cycles [J].

Borowiecki, Mieczyslaw ;

Fiedorowicz, Anna .

DISCRETE MATHEMATICS, 2010, 310 (09) :1445-1455

[7]

Cohen N., 2009, ELECT NOTES DISCRETE, V34, P417, DOI [10.1016/j.endm.2009.07.069, DOI 10.1016/J.ENDM.2009.07.069]

[8]

COHEN N., 2009, RR6876 INRIA

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

Dong, Wei ;

Xu, Baogang .

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

[10]

Fiamcik J., 1978, Math Slovaca, V28, P139

← 1 2 →