The channel assignment problem for mutually adjacent sites

AbstractFix a finite interference set T of nonnegative integers, 0 ϵ T. A T-coloring of a simple graph G = (V, E) is a function f: V → {0, 1, 2, …} such that for {u, ν} ϵ E(G), |f(u) − f(ν)| ϵ T. Let σn denote the optimal span of the T-colorings f of the complete graph Kn, that is, σn = minf{maxu, ν ϵ V|f(u) − f(ν)|}. It was shown by Rabinowitz and Proulx that the asymptotic coloring efficiency rt(T) ≔ limn → ∝(nσn) exists for every set T. We prove the stronger result that the difference sequence {σn + 1 − σn}n = 1∞ is eventually periodic for any T. The entire sequence σ ≔ (σn)n − 1∞ is determined by a finite number of coloring strategies. The greedy (first-fit) T-coloring of Kn 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