کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420290 683916 2006 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Coloring mixed hypertrees
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Coloring mixed hypertrees
چکیده انگلیسی

A mixed hypergraph is a triple (V,C,D)(V,C,D) where VV is its vertex set and CC and DD are families of subsets of VV, called CC-edges and DD-edges, respectively. For a proper coloring, we require that each CC-edge contains two vertices with the same color and each DD-edge contains two vertices with different colors. The feasible set of a mixed hypergraph is the set of all kk's for which there exists a proper coloring using exactly kk colors. A hypergraph is a hypertree if there exists a tree such that the edges of the hypergraph induce connected subgraphs of the tree.We prove that feasible sets of mixed hypertrees are gap-free, i.e., intervals of integers, and we show that this is not true for precolored mixed hypertrees. The problem to decide whether a mixed hypertree can be colored by kk colors is NP-complete in general; we investigate complexity of various restrictions of this problem and we characterize their complexity in most of the cases.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 4, 15 March 2006, Pages 660–672
نویسندگان
, , , ,