Let $G$ be a graph embedded on a surface $S_\varepsilon$ with Euler genus $\varepsilon > 0$, and let $P\subset V(G)$ be a set of vertices mutually at distance at least 4 apart. Suppose all vertices of $G$ have $H(\varepsilon)$-lists and the vertices of $P$ are precolored, where $H(\varepsilon)=\Big\lfloor\frac{7 + \sqrt{24\varepsilon + 1}}{2}\Big\rfloor$ is the Heawood number. We show that the coloring of $P$ extends to a list-coloring of $G$ and that the distance bound of 4 is best possible. Our result provides an answer to an analogous question of Albertson about extending a precoloring of a set of mutually distant vertices in a planar graph to a 5-list-coloring of the graph and generalizes a result of Albertson and Hutchinson to list-coloring extensions on surfaces.
@article{10_37236_2487,
author = {Alice M. Dean and Joan P. Hutchinson},
title = {List-coloring graphs on surfaces with varying list-sizes},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {4},
doi = {10.37236/2487},
zbl = {1266.05028},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2487/}
}
TY - JOUR
AU - Alice M. Dean
AU - Joan P. Hutchinson
TI - List-coloring graphs on surfaces with varying list-sizes
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/2487/
DO - 10.37236/2487
ID - 10_37236_2487
ER -
%0 Journal Article
%A Alice M. Dean
%A Joan P. Hutchinson
%T List-coloring graphs on surfaces with varying list-sizes
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2487/
%R 10.37236/2487
%F 10_37236_2487
Alice M. Dean; Joan P. Hutchinson. List-coloring graphs on surfaces with varying list-sizes. The electronic journal of combinatorics, Tome 19 (2012) no. 4. doi: 10.37236/2487
