# Algorithm for 2-coloring classes of 3-uniform hypergraphs

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

• Please define 2-colouring for hypergraphs. There are many definitions around. Aug 29, 2015 at 9:55
• By "coloring" I mean a coloring of the vertices such that there is no monochromatic edge. Aug 29, 2015 at 10:02
• you should rather post on cstheory.stackexchange.com Oct 9, 2015 at 7:51

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