4
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ Aren't there polytime results on the colorability of planar graphs? Gerhard "Or Some Similar Planar Result" Paseman, 2012.11.16 $\endgroup$ Nov 17, 2012 at 0:19
  • $\begingroup$ It's not about coloring planar graphs per se (see Brendan McKay's answer) $\endgroup$ Nov 18, 2012 at 5:42

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$ Nov 18, 2012 at 5:43
  • $\begingroup$ @Suresh: 2-colorability is also NP-complete for $3$-uniform hypergraphs. $\endgroup$
    – domotorp
    Dec 2, 2016 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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