Coloring face hypergraphs on surfaces (Q703607)

The face hypergraph of a graph \(G\) embedded on a surface has the same vertex set as \(G\) and its (hyper)edges are the sets of vertices forming the faces of \(G\). A hypergraph is \(k\)-choosable if for each assignment of lists of size \(k\) to its vertices each vertex can receive a color from its list such that each edge has at least 2 vertices of different color. In this paper the Lovász local lemma is used to show that if \(G\) is embedded in a surface of genus \(g\) and each face is incident to at least \(r\) vertices, then the face hypergraph is \(O(g^{1/r})\)-choosable. This is asymptotically optimal since it can be seen that there are such graphs requiring \(\Omega(g^{1/r})\) colors. As a special case it follows that the face hypergraph of a triangulation of a surface of genus \(g\) is \(O(\root 3\of g)\)-choosable. This answers a question of this reviewer and \textit{R. Ramamurthi} [J. Comb. Theory, Ser. B 85, 307--337 (2002; Zbl 1029.05057)] who gave examples of triangulations whose face hypergraph requires \(\Omega(\root 3\of g)\) colors. Combining these results gives the maximum number of colors required for triangulations of a fixed surface within a factor of roughly 2. Exact answers remain hard to obtain, but the authors also show that 3 colors suffice for triangulations of a surface with Euler genus 3, as well as several other bounds.