Let G be a graph in which each vertex v has a positive integer weight b(v) and each edge (v, w) has a nonnegative integer weight b(v, w). A bandwidth consecutive multicoloring, simply called a b-coloring of G, assigns each vertex v a specified number b(v) of consecutive positive integers as colors of v so that, for each edge (v, w), all integers assigned to vertex v differ from all integers assigned to vertex w by more than 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. (C) 2015 Elsevier B.V. All rights reserved.
展开▼
