most recent 30 from http://mathoverflow.net 2013-05-24T21:13:47Z http://mathoverflow.net/feeds/question/112626 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112626/2-coloring-a-planar-hypergraph Suresh Venkat 2012-11-17T00:10:47Z 2012-11-17T09:10:25Z

<p>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. </p> <p>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. </p> <p><a href="http://www.cs.elte.hu/~lovasz/scans/covercolor.pdf" rel="nofollow">It is known that $2$-coloring a hypergraph of rank 3 is NP-complete</a>. </p> <p>Is there anything known about the complexity of 2-coloring a <em>planar</em> hypergraph of rank 3 ? </p>

http://mathoverflow.net/questions/112626/2-coloring-a-planar-hypergraph/112642#112642 Brendan McKay 2012-11-17T03:50:59Z 2012-11-17T09:10:25Z

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