Acyclic Edge colorings of 2-degenerate graphs
| dc.creator | Basavaraju, Manu | |
| dc.creator | Chandran, L. Sunil | |
| dc.date | 2008-03-17 | |
| dc.date | 2008-10-20 | |
| dc.date.accessioned | 2026-07-07T10:11:09Z | |
| dc.date.available | 2026-07-07T10:11:09Z | |
| dc.description | 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 Δ+2$, where $Δ=Δ(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 $Δ$, then $a'(G)\le Δ+ 1$. | |
| dc.description | 21 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/0803.2433 | |
| dc.identifier | http://arxiv.org/abs/0803.2433 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/171776 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 | |
| dc.title | Acyclic Edge colorings of 2-degenerate graphs | |
| dc.type | text |