THE CHANNEL ASSIGNMENT PROBLEM FOR MUTUALLY ADJACENT SITES

Fix a finite interference set T of nonnegative integers, 0 is-an-element-of T. A T-coloring of a simple graph G = (V, E) is a function f: V --> (0, 1, 2.... ) such that for {u, v} is-an-element-of E(G), \f(u) - f(v)\ not-an-element-of T. Let sigma(n) denote the optimal span of the T-colorings f of the complete graph K(n), that is, sigma(n) = min(f)(max(u,v is-an-element-of V)\f(u) - f(v)\}. It was shown by Rabinowitz and Proulx that the asymptotic coloring efficiency rt(T) := lim(n-->infinity)(n/sigma(n)) exists for every set T. We prove the stronger result that the difference sequence {sigma(n+1)-sigma(n)}n=1infinity, is eventually periodic for any T. The entire sequence sigma := (sigma(n))n=1infinity is determined by a finite number of coloring strategies. The greedy (first-fit) T-coloring of K(n) also leads to an eventually periodic sequence. We prove these results by studying a special directed graph D(T). Earlier work of Cantor and Gordon on sequences with missing differences in T is discussed in connection with T-coloring. (C) 1994 Academic Press. Inc.