The Complexity of 2-Coloring and Strong Coloring in Uniform Hypergraphs of High Minimum Degree.

In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c(r-1|V(H)|-1 minimum degree of a pair of vertices at least c(r-2|V(H)|-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain the first optimal dichotomy results for 2-colorings of r-uniform hypergraphs. For each problem and each r ≥ 3, we determine a threshold value depending on r such that the problem is NP-complete for c below the threshold, while for c strictly above the threshold it is polynomial. We provide an algorithm constructing the coloring with time complexity O(nC), for some C = C(c, r) > 0. This algorithm becomes more efficient in cases r = 3,4, 5 due to known Turán numbers of the triangle and the Fano plane. In addition, we determine the computational complexity of strong coloring of 3-uniform hypergraphs H with minimum vertex degree at least c(2|V(H)|-1, for some c, leaving a gap for k ≥ 5, which vanishes as k →∞. [ABSTRACT FROM AUTHOR]