Acyclic List Edge Coloring of Graphs. Issue 3 (18th May 2012)

• Record Type: Journal Article
• Authors: Lai, Hsin-Hao; Lih, Ko-Wei
• Is Part Of: Journal of graph theory. Volume 72:Issue 3(2013)
• Page Start: 247
• Page End: 266
• Publication Date: 2012-05-18
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21641
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A proper edge coloring of a graph is said to be <italic>acyclic</italic> if any cycle is colored with at least three colors. An <italic>edge-list L</italic> of a graph <italic>G</italic> is a mapping that assigns a finite set of positive integers to each edge of <italic>G</italic>. An acyclic edge coloring ϕ of <italic>G</italic> such that <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1qdz9gv6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21641:equation:jgt21641-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ϕ</mml:mi><mml:mo>(</mml:mo><mml:mi>e</mml:mi><mml:mo>)</mml:mo><mml:mo>∈</mml:mo><mml:mi>L</mml:mi><mml:mo>(</mml:mo><mml:mi>e</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> for any <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1qdz9gtn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21641:equation:jgt21641-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>e</mml:mi><mml:mo>∈</mml:mo><mml:mi>E</mml:mi><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> is called an <italic>acyclic L</italic><italic>-edge coloring</italic> of <italic>G</italic>. A graph <italic>G</italic> is said to be <italic>acyclically k</italic><italic>-edge choosable</italic> if it has an acyclic <italic>L</italic>‐edge coloring for any edge‐list <italic>L</italic> that satisfies <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1qdz9gs3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21641:equation:jgt21641-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>|</mml:mo><mml:mi>L</mml:mi><mml:mo>(</mml:mo><mml:mi>e</mml:mi><mml:mo>)</mml:mo><mml:mo>|</mml:mo><mml:mo>⩾</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:math> for each edge <italic>e</italic>. The <italic>acyclic list chromatic index</italic> is the least integer <italic>k</italic> such that <italic>G</italic> is acyclically <italic>k</italic>‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.</p> </abstract>