Acyclic edge coloring of planar graphs with Δ colors

被引：7

作者：

Hudak, David ^{[2
]}

Kardos, Frantisek ^{[2
]}

Luzar, Borut ^{[1
]}

Sotak, Roman ^{[2
]}

Skrekovski, Riste ^{[3
]}

机构：

[1] Inst Math Phys & Mech, Ljubljana, Slovenia

[2] Pavol Jozef Safarik Univ, Fac Sci, Inst Math, Kosice, Slovakia

[3] Univ Ljubljana, Fac Math & Phys, Dept Math, Ljubljana 61000, Slovenia

来源：

DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 09期

关键词：

Acyclic edge coloring; Planar graph; Discharging method;

D O I：

10.1016/j.dam.2012.01.017

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. In 1978, it was conjectured that Delta(G) + 2 colors suffice for an acyclic edge coloring of every graph G (Fiamcik, 1978 [8]). The conjecture has been verified for several classes of graphs, however, the best known upper bound for as special class as planar graphs are, is Delta + 12 (Basavaraju and Chandran, 2009[3]). In this paper, we study simple planar graphs which need only Delta(G) colors for an acyclic edge coloring. We show that a planar graph with girth g and maximum degree Delta admits such acyclic edge coloring if g >= 12, or g >= 8 and Delta >= 4, or g >= 7 and Delta >= 5, or g >= 6 and Delta >= 6, org >= 5 and Delta >= 10. Our results improve some previously known bounds. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：1356 / 1368

页数：13

共 15 条

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