Acyclic List Edge Coloring of Graphs. Issue 3 (18th May 2012) - Lai, Hsin-Hao; Lih, Ko-Wei
Abstract A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ϕ of G such that <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1qdz9gv6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ϕ(e)∈L(e) for any <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1qdz9gtn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />e∈E(G) is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1qdz9gs3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />|L(e)|⩾k for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.