Some Results about Edge-Choosability of Plane Graphs

Jianfeng Hou
School of Mathematics and System Sciences, Shandong University, Jinan 250100, P. R. China


Abstract     Full Text  PDF

Let $G=(V,E)$ be a graph. The mapping $L$ is said to an edge assignment for $G$ if it assigns a list $L(e)$ of possible colors to each edge $e$ of $G$. If $G$ has some proper edge-coloring $\phi$ such that $\phi(e)\in{L(e)}$ for all edge $e$, then we say that $G$ is edge-$L$-colorable, or $\phi$ is an edge-$L$-coloring of $G$. We call $G$ is edge-$k$-choosable if it is edge-$L$-colorable for every edge assignment $L$ satisfying $|L(e)|\geq {k} $ for all edge $e$. The list chromatic index $\chi_l'(G)$ of $G$ is the smallest integer $k$ such that $G$ is edge-$k$-choosable. The following conjecture was formulated independently by Vizing, by Gupta, by Albertson and Collins, and Bollob$\'{a}$s and Harris and it is well know as the list coloring conjecture.
Conjecture A. If $G$ is a multigraph, then $\chi_l'(G)=\chi'(G)$.
This conjecture has been proved for a few special cases. For (simple) graphs, Vizing proposed a weaker conjecture as following.
Conjecture B. Every graph $G$ is edge-$\Delta(G)+1$-choosable.
Some results for edge-choosability of some plane graphs are given.