Question

Consider a hypergraph (of rank 3) $H = (V, E)$ (where the rank of $H$ is the maximum cardinality of a hyperedge). $H$ is said to be planar if we can construct a planar graph $G = (V, A)$, and a mapping $f$ from $E$ to the faces of $G$ such that $v \in E$ iff $v$ is adjacent to $f(E)$ in the drawing.

Further, a hypergraph is said to be 2-colorable if there is an assignment of the colors R, B to the vertices so that no edge is monochromatic.

It is known that $2$-coloring a hypergraph of rank 3 is NP-complete.

Is there anything known about the complexity of 2-coloring a planar hypergraph of rank 3 ?

Answer 1

I might be missing something, but it seems to be the question of whether a planar graph with faces of size at most 3 can be vertex-coloured so that no face is monochromatic. If there are only faces of size 3 (a triangulation) it is easy: use 4CT to properly colour with four colours $a,b,c,d$ then change $c$ into $a$ and $d$ into $b$. Each face now has both $a$ and $b$. If there are also faces of size 2, this is insufficient.

ADDED: This argument also doesn't work if the planar graph is not 2-connected, as there might be faces of length greater than 3 that have only 3 distinct vertices on their boundaries, like a face 1–2–3–2–1 (where 2 is a cut vertex).