کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435665 | 689924 | 2015 | 13 صفحه PDF | دانلود رایگان |
Let G be a graph in which each vertex v has a positive integer weight b(v)b(v) and each edge (v,w)(v,w) has a nonnegative integer weight b(v,w)b(v,w). A bandwidth consecutive multicoloring, simply called a b-coloring of G, assigns each vertex v a specified number b(v)b(v) of consecutive positive integers as colors of v so that, for each edge (v,w)(v,w), all integers assigned to vertex v differ from all integers assigned to vertex w by more than b(v,w)b(v,w). The maximum integer assigned to vertices is called the span of the coloring. The b-coloring problem asks to find a b-coloring of a given graph G with the minimum span. In the paper, we present four efficient approximation algorithms for the problem, which have theoretical performance guarantees for the computation time, the span of a found b-coloring and the approximation ratio. We also obtain several upper bounds on the minimum span, expressed in terms of the maximum b-degrees, one of which is an extension of Brooks' theorem on an ordinary coloring.
Journal: Theoretical Computer Science - Volume 607, Part 2, 23 November 2015, Pages 208–220