Premium
Acyclic List Edge Coloring of Graphs
Author(s) -
Lai Hsin-Hao,
Lih Ko-Wei
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21641
Subject(s) - combinatorics , edge coloring , mathematics , 1 planar graph , discrete mathematics , directed acyclic graph , graph coloring , chordal graph , list coloring , graph , line graph , graph power
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 ϕ ( e ) ∈ L ( e ) for any 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 | 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.