MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.