# 2-Coloring a planar hypergraph

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.

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

-
Aren't there polytime results on the colorability of planar graphs? Gerhard "Or Some Similar Planar Result" Paseman, 2012.11.16 – Gerhard Paseman Nov 17 '12 at 0:19
It's not about coloring planar graphs per se (see Brendan McKay's answer) – Suresh Venkat Nov 18 '12 at 5:42

## 1 Answer

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).

-
I see. the problem is that a rank three hypergraph will have edges of size 2 as well (in fact these are used in the NP-completeness for general hypergraphs) – Suresh Venkat Nov 18 '12 at 5:43