The face-hypergraph of a graph G embedded on a surface has the same vertex-set as G and every face of G corresponds to an edge of the face-hypergraph consisting of the vertices incident to the face. We study coloring parameters of these embedded hypergraphs.A hypergraph is weakly k-colorable (weakly k-choosable) if there is a coloring of its vertices from a set of k colors (from every assignment of lists of size k to its vertices) such that no edge is monochromatic. Thus a weak coloring of a face-hypergraph corresponds to a vertex coloring of the underlying graph such that no face is monochromatic.
We show that hypergraphs can be extended to face-hypergraphs in a natural way and use tools from topological graph theory, the theory of hypergraphs and design theory to obtain general bounds for the coloring and choosability problems. To show the sharpness of several bounds, we construct for every even n, an n-vertex triangulation of a surface such that every triple is a face exactly once.
We provide supporting evidence for our conjecture that every plane face-hypergraph is weakly 2-choosable and we pose several open questions, most notably: Can the vertices of a planar graph always be properly color from lists of size 4, with the restriction on the lists that the colors come in pairs and a color is in a list if and only if its twin color is? An affirmative answer to this question would imply our conjecture, as well as the Four Color Theorem and several open problems.