An Asymptotic Approach to the Channel Assignment Problem

Abstract

This paper introduces a new approach to the T-coloring problem for complete graphs. The problem arises from Hale’s formulation of the channel assignment problem for potentially interfering communication nets. The motivating result of this paper is that the T-span of $K_n $, denoted $\operatorname{sp}_T ( K_n )$, is asymptotically independent of n. More precisely, each T-set has a rate, $\operatorname{rt} ( T )$, and $n /\operatorname{sp}_T ( K_n )$ converges to $\operatorname{rt} ( T )$. We introduce a finite algorithm for computing the rate of T. This is accomplished by associating to a given set T an infinite sequence of integers with the property that the first n integers of this sequence T-color $K_n $ in an asymptotically optimal way. Lastly, we compute $\operatorname{rt} ( T )$ or bounds on its value for some interesting special cases of sets T.