Computer Science – Discrete Mathematics
Scientific paper
2010-07-14
Computer Science
Discrete Mathematics
16 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. If every induced subgraph $H$ of $G$ satisfies the condition $\vert E(H) \vert \le 2\vert V(H) \vert -1$, we say that the graph $G$ satisfies $Property\ A$. In this paper, we prove that if $G$ satisfies $Property\ A$, then $a'(G)\le \Delta + 3$. Triangle free planar graphs satisfy $Property\ A$. We infer that $a'(G)\le \Delta + 3$, if $G$ is a triangle free planar graph. Another class of graph which satisfies $Property\ A$ is 2-fold graphs (union of two forests).
Basavaraju Manu
Chandran Sunil L.
No associations
LandOfFree
Acyclic Edge Coloring of Triangle Free 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 Triangle Free Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic Edge Coloring of Triangle Free Planar Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-120495