Manuel Bodirsky

The No-rainbow-coloring Problem

This is a computational problem in NP of unknown computational complexity. It is an important open case for the classification of the surjective constraint satisfaction problem for 3-element domain, but appeared in equivalent form in the graph coloring literature, and in a paper on graph matchings.

Input:

A 3-uniform hypergraph with vertices V (that is, all hyperedges in the hypergraph contain exactly three elements).

Question:

Is there a partition of V into three non-empty subsets A,B,C of V such that no edge is 'rainbow-colored', i.e., no edge contains one vertex from each of A,B,C.

Remarks:

The problem is known to be NP-complete when some of the elements of V can be forced to belong to one of the parts A,B,C.