Approximate L(δ1, δ2,..., δt)-coloring of trees and interval graphs

Given a vector (delta(1), delta(2),...,delta(t)) of nonincreasing positive integers, and an undirected graph G = (11, E), an L(delta(1), delta(2),..., delta(t))-coloring of G is a function f from the vertex set V to a set of nonnegative integers such that vertical bar f(u) - f (v)vertical bar >= delta(i), if d(u, v) = i, I <= i <= t, where d(u, v) is the distance (i.e., the minimum number of edges) between the vertices u and v. An optimal L(delta(1), delta(2),...,delta(t))-coloring for G is one minimizing the largest integer used over all such colorings. Such a coloring problem has relevant applications in channel assignment for interference avoidance in wireless networks. This article presents efficient approximation algorithms for coloring of two relevant classes of graphs-trees, and interval graphs. Specifically, based on the notion of strongly simplicial vertices, O(n(t+delta(1))) and O(nt(2)delta(1)) time algorithms are proposed to find alpha-approximate colorings on interval graphs and trees, respectively, where n is the number of vertices and a is a constant depending on t and delta(1),..., delta(t). Moreover, an O(n) time algorithm is given for the L(delta(1), delta(2))-coloring of unit interval graphs, which provides a 3-approximation. (c) 2007 Wiley Periodicals, Inc.