Mathematics – Combinatorics
Scientific paper
2008-03-17
Mathematics
Combinatorics
21 pages, 3 figures
Scientific paper
An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycle s. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic e dge coloring using k colors and is denoted by $a'(G)$. A graph is called 2-$degenerate$ if any of its induced subgraph has a vertex of degree at most 2. The class of 2-$degenerate graphs$ properly conta in $series$-$parallel graphs$, $outerplanar graphs$, \emph{non-regular subcubic graphs}, \emph{planar graphs of girth at least 6} and \emph{circle graphs of girth at least 5} as subclasses. It was conjectur ed by Alon, Sudakov and Zaks (and earlier by Fiamcik) that $a'(G)\le \Delta+2$, where $\Delta =\Delta(G)$ denotes the maximum deg ree of the graph. We prove the conjecture for 2-$degenerate$ graphs: in fact we prove a stronger bound . We prove that if $G$ is a 2-degenerate graph with maximum degree $\Delta$, then $a'(G)\le \Delta + 1$.
Basavaraju Manu
Chandran Sunil L.
No associations
LandOfFree
Acyclic Edge colorings of 2-degenerate 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 colorings of 2-degenerate graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic Edge colorings of 2-degenerate graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-646201