H-colorings of dense hypergraphs
For r >= 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 > 0 the problem of deciding whether an n-vertex r-uniform hypergraph G of minimum vertex degree delta(G) >= C((n-1)(r-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. (C) 2012 Elsevier B.V. All rights reserved.
dense hypergraph graph algorithms hypergraph homomorphism (h-coloring)