H-colorings of dense hypergraphs

For r⩾3r⩾3, we study the H-coloring problem on r-uniform hypergraphs with large vertex degrees. Under certain restrictions on the structure of H  , it is proved that for every c>0c>0 the problem of deciding whether an n-vertex r-uniform hypergraph G   of minimum vertex degree δ(G)⩾c(n−1r−1) is H-colorable is in P. Our results seem to be the first complexity theoretic results for the H-coloring problem on dense hypergraphs.

► We present two polynomial-time algorithms for deciding the existence of a homomorphism of a dense r-uniform n-vertex hypergraph F to a special graph H. ► The target graph H is specified by some restrictions on its maximum collective degree. ► We provide a polynomial time counting algorithm for the number of such homomorphisms.