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 ?

Improve this question
$\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$
    – Gerhard Paseman
    Commented Nov 17, 2012 at 0:19
  • $\begingroup$ It's not about coloring planar graphs per se (see Brendan McKay's answer) $\endgroup$
    – Suresh Venkat
    Commented Nov 18, 2012 at 5:42

1 Answer 1

Reset to default
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).

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .