Acyclic list edge coloring of planar graphs
by
Hsin-Hao Lai
Ko-Wei Lih
Vol. 5 No. 4 (2010) P.413~P.436
ABSTRACT
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.
KEYWORDS
Acyclic list edge colorings, planar graphs
MATHEMATICAL SUBJECT CLASSIFICATION 2010
Primary: 05C15, 05C10, 05C75
MILESTONES
Received: 2010-12-24
Revised :
Accepted: 2010-12-28
Download Full Content