کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872319 | 681740 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Interval incidence coloring of bipartite graphs
ترجمه فارسی عنوان
رنگ آمیزی بسامد فاصله گراف دو طرفه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی بروز مصاحبه، نمودار دو طرفه، نمودارهای زیرمجموعه، درختان،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper1 we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (Ïii) for bipartite graphs Ïiiâ¤2Î, and we prove that Ïii=2Î holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic bipartite graphs. We also study the problem for bipartite graphs with Î=4 and we show that 5-coloring is easy and 6-coloring is hard (NP-complete). Moreover, we construct an O(nÎ3.5logÎ) time optimal algorithm for trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 166, 31 March 2014, Pages 131-140
Journal: Discrete Applied Mathematics - Volume 166, 31 March 2014, Pages 131-140
نویسندگان
Robert Janczewski, Anna MaÅafiejska, MichaÅ MaÅafiejski,