Article ID Journal Published Year Pages File Type
417935 Discrete Applied Mathematics 2016 20 Pages PDF
Abstract

An acyclic edge coloring of a graph GG is a proper edge coloring such that every cycle is colored with at least three colors. The acyclic chromatic index χa′(G) of a graph GG is the least number of colors in an acyclic edge coloring of GG. It was conjectured that χa′(G)≤Δ(G)+2 for any simple graph GG with maximum degree Δ(G)Δ(G). In this paper, we prove that every planar graph GG admits an acyclic edge coloring with Δ(G)+6Δ(G)+6 colors.

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