id: 06004146
dt: j
an: 06004146
au: Basavaraju, Manu; Chandran, L. Sunil
ti: Acyclic edge coloring of 2-degenerate graphs.
so: J. Graph Theory 69, No. 1-2, 1-27 (2012).
py: 2012
pu: John Wiley \& Sons, New York, NY
la: EN
cc: 
ut: acyclic edge coloring; acyclic edge chromatic number; 2-degenerate graphs;
    series; parallel graphs; outer planar graphs
ci: 
li: doi:10.1002/jgt.20559
ab: Summary: An acyclic edge coloring of a graph is a proper edge coloring such
    that there are no bichromatic cycles. The 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)$. 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 contains
    series-parallel graphs, outerplanar graphs, non-regular subcubic
    graphs, planar graphs of girth at least 6 and circle graphs of girth at
    least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks
    (and much earlier by Fiamcik) that $a’(G)\leqΔ+2$, where $Δ= Δ(G)$
    denotes the maximum degree 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)\leqΔ+1$.
rv: