Improper choosability of graphs embedded on the surface of genus \(r\) (Q1402089): Difference between revisions

A list assignment of a graph \(G\) is a function \(L\) that assigns a list \(L(v)\) of colors to each vertex \(v\) of \(G\). An \((L,d)^\ast\)-coloring is a mapping \(\phi\) that assigns a color \(\phi(v) \in L(v)\) to each vertex \(v\) of \(G\) such that \(v\) has at most \(d\) neighbors colored with \(\phi(v)\). A graph \(G\) is \((m,d)^\ast\)-choosable if there exists an \((L,d)^\ast\)-coloring for every list assignment \(L\) with \(|L(v)|=m\) for very vertex \(v\) of \(G\). Let \(G\) be a graph on a surface of genus \(r \geq 2\). This paper establishes the following results. (1) \(G\) is \((2,1)^\ast\)-choosable if \(g(G) \geq r +9\) and \(|F|\geq 21\). (2) \(G\) is \((2,2)^\ast\)-choosable if \(g(G) \geq \lceil \frac{6}{5}(r+5) \rceil\) and \(|F|\geq 13\). (3) \(G\) is \((2,3)^\ast\)-choosable if \(g(G) \geq r+5\) and \(|F|\geq 13\).