کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418971 | 681728 | 2008 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Vertex coloring acyclic digraphs and their corresponding hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Vertex coloring acyclic digraphs and their corresponding hypergraphs Vertex coloring acyclic digraphs and their corresponding hypergraphs](/preview/png/418971.png)
چکیده انگلیسی
We consider vertex coloring of an acyclic digraph G⇒ in such a way that two vertices which have a common ancestor in G⇒ receive distinct colors. Such colorings arise in a natural way when bounding space for various genetic data for efficient analysis. We discuss the corresponding down-chromatic number and derive an upper bound as a function of D(G⇒), the maximum number of descendants of a given vertex, and the degeneracy of the corresponding hypergraph. Finally, we determine an asymptotically tight upper bound of the down-chromatic number in terms of the number of vertices of G⇒ and D(G⇒).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 10, 28 May 2008, Pages 1918–1928
Journal: Discrete Applied Mathematics - Volume 156, Issue 10, 28 May 2008, Pages 1918–1928
نویسندگان
Geir Agnarsson, Ágúst S. Egilsson, Magnús M. Halldórsson,