The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree

摘要

In this note 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∣),has a vertex 2-coloring and a strong vertex κ-coloring. Moti-vated by an old result of Edwards for graphs, we summarize what can be deduced from his method about the complexity of these problems for hy-pergraphs. We obtain the first optimal dichotomy results for 2-colorings of 3- and 4-uniform hypergraphs according to the value of c. In addi-tion, we determine the computational complexity of strong κ-colorings of 3-uniform hypergraphs for some c, leaving a gap which vanishes as k → ∞.