Acyclic list edge coloring of planar graphs
by Hsin-Hao Lai   Ko-Wei Lih  

Vol. 5 No. 4 (2010) P.413~P.436


A proper edge coloring of a graph is said to be ${\it acyclic}$ if any cycle is colored with at least three colors. The ${\it acyclic \ chromatic \ index}$, denoted $a'(G)$, is the least number of colors required for an acyclic edge coloring of $G$. An ${\it 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 $\phi$ of $G$ such that $\phi(e)\in L(e)$ for any $e\in E(G)$ is called an ${\it acyclic \ L-edge \ coloring}$ of $G$. A graph $G$ is said to be ${\it acyclically \ k-edge \ choosable}$ if it has an acyclic $L$-edge coloring for any edge-list $L$ that satisfies $|L(e)| \geqslant k$ for each edge $e$. The ${\it acyclic \ list \ chromatic \ index}$ is the least integer $k$ such that $G$ is acyclically $k$-edge choosable. In [2, 3, 4, 7, 10, 11, 12], upper bounds for the acyclic chromatic index of several classes of planar graphs were obtained. In this paper, we generalize these results to the acyclic list chromatic index of planar graphs.

Acyclic list edge colorings, planar graphs

Primary: 05C15, 05C10, 05C75


Received: 2010-12-24
Revised :
Accepted: 2010-12-28

Download Full Content