Article ID Journal Published Year Pages File Type
427960 Information Processing Letters 2010 6 Pages PDF
Abstract

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. The acyclic chromatic index of a graph G, denoted by α′(G), is the minimum number k such that G admits an acyclic edge coloring using k colors. Let G be a plane graph with maximum degree Δ and girth g. In this paper, we prove that α′(G)=Δ(G) if one of the following conditions holds: (1) Δ⩾8 and g⩾7; (2) Δ⩾6 and g⩾8; (3) Δ⩾5 and g⩾9; (4) Δ⩾4 and g⩾10; (5) Δ⩾3 and g⩾14. We also improve slightly a result of A. Fiedorowicz et al. (2008) [7] by showing that every triangle-free plane graph admits an acyclic edge coloring using at most Δ(G)+5 colors.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics