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

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

1 Answer 1

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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