Acyclic Edge coloring of Planar Graphs

Details Acyclic Edge coloring of Planar Graphs Acyclic Edge coloring of Planar Graphs

2009-08-16

arxiv.org/abs/0908.2237v1

Computer Science

Discrete Mathematics

10 pages. 0 figures

Scientific paper

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that $a'(G)\le \Delta+2$, where $\Delta =\Delta(G)$ denotes the maximum degree of the graph. We prove that if $G$ is a planar graph with maximum degree $\Delta$, then $a'(G)\le \Delta + 12$.

Affiliated with

Also associated with

No associations

Rating

Acyclic Edge coloring of Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Acyclic Edge coloring of Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic Edge coloring of Planar Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704685