ACYCLIC EDGE-COLORING OF PLANAR GRAPHS

被引：34

作者：

Basavaraju, Manu ^{[1
]}

Chandran, L. Sunil ^{[1
]}

Cohen, Nathann ^{[2
,3
]}

Havet, Frederic ^{[2
,3
]}

Mueller, Tobias ^{[4
]}

机构：

[1] Indian Inst Sci, Comp Sci & Automat Dept, Bangalore 560012, Karnataka, India

[2] UNSA, CNRS, I3S, Projet Mascotte, F-06902 Sophia Antipolis, France

[3] INRIA, F-06902 Sophia Antipolis, France

[4] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Sch Math, IL-69978 Tel Aviv, Israel

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2011年 / 25卷 / 02期

关键词：

edge-coloring; planar graphs; bounded density graphs; CHROMATIC NUMBER;

D O I：

10.1137/090776676

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph G, denoted. chi'(alpha)(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Delta(G) is large enough, then chi'(alpha) (G) = Delta (G). We settle this conjecture for planar graphs with girth at least 5. We also show that chi'(alpha) (G) <= Delta (G) + 12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan [Inform. Process. Lett., 108 (2008), pp. 412-417].

引用

页码：463 / 478

页数：16

共 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] Acyclic edge coloring of 2-degenerate graphs [J].

Basavaraju, Manu ;

Chandran, L. Sunil .

JOURNAL OF GRAPH THEORY, 2012, 69 (01) :1-27

[4] d-Regular Graphs of Acyclic Chromatic Index at Least d+2 [J].

Basavaraju, Manu ;

Chandran, L. Sunil ;

Kummini, Manoj .

JOURNAL OF GRAPH THEORY, 2010, 63 (03) :226-230

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

Burnstein M.I., 1979, SOOBSC AKAD NAUK GRU, V93, P21

[8] About acyclic edge colourings of planar graphs [J].

Fiedorowicz, Anna ;

Haluszczak, Mariusz ;

Narayanan, Narayanan .

INFORMATION PROCESSING LETTERS, 2008, 108 (06) :412-417

[9]

FLAMCIK J, 1978, MATH SLOVACA, V28, P139

[10]

FLAMCIK J, 1980, ARCH MATH BRNO, V16, P81

← 1 2 →