On irreducible no‐hole L(2, 1)‐coloring of trees
Renu C. Laskar, Gretchen L. Matthews, Beth Novick, John Villalpando · Networks · 2008
Abstract We consider a variant of the channel assignment problem in which frequencies are assigned to transmitters in a way that avoids interference while ensuring that all frequencies within the bandwidth are used. This is modeled as an L(2, 1)‐coloring of a graph which is no‐hole and irreducible in the sense that no color can be replaced with a smaller one. In this article, we show that if the network is any tree other than a star, then frequencies may be assigned in this fashion without increasing the bandwidth; that is, we show that for any such tree T, the inh‐span of T is equal to its span. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009