کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427671 | 686540 | 2012 | 4 صفحه PDF | دانلود رایگان |

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.
Journal: Information Processing Letters - Volume 112, Issue 23, 15 December 2012, Pages 899–902