کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427671 686540 2012 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
H-colorings of dense hypergraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 23, 15 December 2012, Pages 899–902
نویسندگان
,