2010 / December Volume 5 No.4
Acyclic list edge coloring of planar graphs
| Published Date |
2010 / December
|
|---|---|
| Title | Acyclic list edge coloring of planar graphs |
| Author | |
| Keyword | |
| Download | |
| Pagination | 413-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.
|
| AMS Subject Classification |
05C15, 05C10, 05C75
|
| Received |
2010-12-24
|
| Accepted |
2010-12-28
|