Acyclic List Edge Coloring of Graphs |
| |
Authors: | Hsin-Hao Lai Ko-Wei Lih |
| |
Affiliation: | 1. DEPARTMENT OF MATHEMATICS, NATIONAL KAOHSIUNG NORMAL UNIVERSITY, , YANCHAO, KAOHSIUNG, 824 TAIWAN;2. INSTITUTE OF MATHEMATICS, ACADEMIA SINICA, , TAIPEI, 10617 TAIWAN |
| |
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 for any 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 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. |
| |
Keywords: | acyclic edge coloring acyclic list chromatic index outerplanar graph subcubic graph Halin graph |
|
|