Approximate L(?1, ?2, . . . , ?t)-Coloring of Trees and Interval Graphs

Given a vector (?1 , ?2 , . . . , ?t ) of nonincreasing positive integers, and an undirected graph G = (V , E ), an L(?1 , ?2 , . . . , ?t )-coloring of G is a function f from the ver- tex set V to a set of nonnegative integers such that |f (u ) - f (v )| >= ?i , if d (u , v ) = i , 1 <= 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(?1 , ?2 , . . . , ?t )- coloring for G is one minimizing the largest integer used over all such colorings. Such a coloring problem has rele- vant applications in channel assignment for interference avoidance in wireless networks. This article presents efficient approximation algorithms for L(?1 , ?2 , . . . , ?t )- coloring of two relevant classes of graphs--trees, and interval graphs. Specifically, based on the notion of strongly simplicial vertices, O (n(t +?1 )) and O (nt 2 ?1 ) time algorithms are proposed to find ?-approximate colorings on interval graphs and trees, respectively, where n is the number of vertices and ? is a constant depending on t and ?1 , . . . , ?t . Moreover, an O (n) time algorithm is given for the L(?1 , ?2 )-coloring of unit interval graphs, which provides a 3-approximation. Specifically, based on the notion of strongly simplicial vertices, O (n(t +δ1 )) and O (nt 2 δ1 ) time algorithms are proposed to find α-approximate colorings on interval graphs and trees, respectively, where n is the number of vertices and α is a constant depending on t and δ1 , . . . , δt . Moreover, an O (n) time algorithm is given for the L(δ1 , δ2 )-coloring of unit interval graphs, which provides a 3-approximation. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 204-216 2007