5
$\begingroup$

Hi all and thanks in advance for your efforts.

I'm interested in 2-coloring 3-uniform hypergraphs. I know that in general, the problem of deciding if a 3-uniform hypergraph is 2-colorable is NP-hard. I wonder if there are any (non-trivial) subclasses of 3-uniform hypergraphs for which there exists a polynomial algorithm for 2-coloring. For example, are there some $H_1,...,H_k$ for which the class of $(H_1,...,H_k)$-free 3-uniform hypergraphs has a polynomial algorithm for 2-coloring? Are there any results of this type?

Thanks, Lior

$\endgroup$
  • 1
    $\begingroup$ Please define 2-colouring for hypergraphs. There are many definitions around. $\endgroup$ – Brendan McKay Aug 29 '15 at 9:55
  • $\begingroup$ By "coloring" I mean a coloring of the vertices such that there is no monochromatic edge. $\endgroup$ – user78647 Aug 29 '15 at 10:02
  • $\begingroup$ you should rather post on cstheory.stackexchange.com $\endgroup$ – Florent Foucaud Oct 9 '15 at 7:51
1
$\begingroup$

This problem is the same as MONOTONE NOT-ALL-EQUAL-3-SAT (perhaps you will find useful references by searching for this problem), where you have a set $C$ of 3-clauses from a variable set $X$ and you want a boolean assignment for $X$ so that each clause contains a true and a false variable ("monotone" stands for "no negated variables").

In this terminology, Moret showed that MONOTONE NOT-ALL-EQUAL-3-SAT is polynomial-time solvable when the clause-variable (bipartite) incidence graph of the instance is planar (Planar NAE3SAT is in P, B. Moret, ACM SIGACT News, Volume 19 Issue 2, Summer 1988).

In the terminology of hypergraph coloring, this translates to the edge-vertex (bipartite) incidence graph of the input hypergraph being planar.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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