List-coloring graphs on surfaces with varying list-sizes (Q1953362)

Summary: 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 \textit{M. O. Albertson} [J. Comb. Theory, Ser. B 73, No. 2, 189--194 (1998; Zbl 0910.05026)] 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 \textit{M. O. Albertson} and \textit{J. P. Hutchinson} [Electron. J. Comb. 9, No. 1, Research paper R37, 10 p. (2002; Zbl 1005.05017)] to list-coloring extensions on surfaces.