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.