Locally planar graphs are 5-choosable (Q958683)

The authors prove that for every surface \(S\) there exists a constant \(w\) such that every graph that can be embedded in \(S\) with edge-width at least \(w\) is \(5\)-choosable. Their proof shows that there exists an algorithm, whose input is a graph \(G\) embedded in a surface of Euler genus \(g\) with edge-width at least \(2^{\Theta(g)}\) and a \(5\)-list-assignment \(L\) for \(G,\) which finds an \(L\)-coloring of \(G\) in polynomial time. As a corollary they obtain that for every surface \(S\) there is a constant \(k\) such that for every graph \(G\) embedded in \(S,\) there exists a vertex set \(U\) of at most \(k\) vertices such that \(G-U\) is \(5\)-choosable. They finally state that for every surface \(S\) there exists an integer \(w\) such that every triangle-free graph \(G\) embedded in \(S\) with edge-width at least \(w\) is \(4\)-choosable. Similary, every graph of girth at least \(6\) embedded in \(S\) with edge-width at least \(w\) is \(3\)-choosable. They also propose the conjecture that for any fixed surface \(S\), there is a polynomial time algorithm to decide whether a given graph embedded on \(S\) is \(5\)-choosable.