Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
417935 | Discrete Applied Mathematics | 2016 | 20 Pages |
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
Tao Wang, Yaqiong Zhang,