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