Cell Phone Tidbit (9/03/03)

Prepared by:

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, New York 11451-0001

email: malkevitch@york.cuny.edu

Cell phone technology gives rise to a large number of interesting mathematical questions. One class of questions concerns the way to design a system that serves a particular geographic area and which can be run as cheaply as possible. What is involved here are issues about the costs of having the region chopped up into few parts versus having the region chopped up into a larger number of parts.

Another class of problems, those which have probably gotten the most mathematical attention concern the issue of maximizing the number of calls that can be handled using a limited piece of the radio frequency band. For traditional radio frequency assignments it was noted relatively early that one could think of this problem as a vertex coloring problem for a graph. The different radio stations are thought of as the vertices of the graph. Two stations are joined by an edge if they are geographically close enough that they would interfere with each other if they got the same frequency, or if for any other reason they are required to be given different frequencies. Now, finding the minimum number of colors necessary to color the resulting graph gives a way of assigning frequencies to the stations so as to avoid interference (or other problems). This minimum number is known as the chromatic number of the graph. Unfortunately, it is known that the problem of finding the vertex chromatic number is NP-complete. This means that it is unlikely that there will ever be found a polynomial time algorithm to find the minimum number of colors as the number of vertices (stations) increases. The issues involved in cell phone technology add further interesting mathematical complexities to this basic coloring problem.

Let us consider a mathematical model of considerable interest which grows out cell phone problems, and which includes as a special case the problem of finding the chromatic number of a graph.

We are given a set of transmitters which are to be assigned one of an available collection of equally spaced frequencies which are numbered from 0 to n. These frequencies are thought of as colors, and each user is represented by a vertex of a graph. Two vertices (transmitters) are joined by an edge when the transmitters they represent must get different frequencies. For a given transmitter u the color assigned to it will be denoted f_u. When one has assigned frequencies to the vertices, since these frequencies are non-negative integers, we can think of there being a distance associated with two transmitters whose vertices are joined by an edge. This distance being the difference (computed so that one gets a non-negative number) in the frequencies which are assigned to them. The prohibited distances can be the same for all edges or can vary from edge to edge. For the edge from v to w the prohibited set of frequencies will be denoted T_vw. Thus, the assignment rule f for colors is required to obey |f_v - f_w| œ T_vw. We always insist, for every edge, that 0 be a member of the prohibited set for that edge. A coloring which obeys these rules is known as a T-coloring. The minimum number of colors used in a T-coloring is denoted by c_T. A theorem of M. Cozzens and F. Roberts shows that for a graph G, c_T(G) = c(G). Thus, perhaps surprisingly, from the perspective of the number of colors needed, one is not "hurt" by having more constraints on assigning colors to the vertices. However, there is another optimization condition that can be considered for the T-coloring environment. The span of a T-coloring is the difference between the largest and smallest color number used in coloring the vertices of the graph. There are simple examples for which there is no coloring that uses the smallest number of colors and simultaneously achieves the smallest span. Further generalizations of this basic framework expand the idea of a T-coloring to a list T-coloring. Here the idea is that there are "blocked" frequencies which can not be assigned to a vertex, so that in trying to achieve a coloring one must limit the choice at each vertex to a list of non-blocked colors (frequencies).

As mentioned above, T-coloring and list T-coloring are generalizations of the ordinary vertex coloring problems where the vertices of a graph are to assigned colors from the set 0, 1, 2, ..., n which can be thought of as frequencies assigned to cell phones. The span of a coloring is the difference between the largest and smallest frequencies used. For each edge, the set assigned to that edge are forbidden values for the absolute value of the difference of the colors used at the end vertices of that edge. Here is an example to illustrate these ideas:

The graph in (a) can be colored with 0, 1, 2 and the span of this coloring is 2. The chromatic number for the graph, thus, is 3 and the span is 2. For the T-coloring problem in (b) the graph can still be colored with only 3 colors but now the span is 3. However, the situation in (b) does not allow one to simultaneously achieve this. The coloring where u is assigned 1, v is assigned 3, x is assigned 5 and w is assigned 1 (which we can represent by (1, 3, 5, 1) = (u, v, x, w)) uses only 3 colors but the span is 4. On the other hand, the colorings (3, 1, 4, 2) or (2, 4, 1, 3) have span 3 but use 4 colors. In fact, any coloring with 3 colors must have span at least 4. The situation in (c) where the list T-chromatic number is 3 but the list T-span value is 4. (Here colors 6 or more are forbidden as are negative integers.)

References:

Borndodörfer, R. and A. Eisenblätter, M. Grötschel, A. Martin, Frequency Assignment in Cellular Phone Networks (preprint).

Cozzens, M. and F. Roberts, T-colorings of graphs and the channel assignment problem, Congr. Numer., 35 (1982) 191-208.

Griggs, J. and D. Liu, Channel assignment problem for mutally adjacent sites, J. Comb. Theory (A) 68 (1994) 169-183.

Hale, W., Frequency assignment: Theory and applications, Proc. IEEE 68 (1980) 1497-1514.

Hu, S. and S-T Juan, G. Chang, T-colorings and T-edge spans of graphs, Graphs and Combinatorics 15 (1999) 295-301.

Liu, D., T-colorings of graphs, Discrete Math., 1001 (1992) 203-212.

Raychaudhuri, A., Further results on T-coloring and frequency assignment problems, SIAM J. Disc. Math., 7 (1994) 605-613.

Tesman, B., T-colorings, list T-colorings, and set T-colorings of graphs, Ph. D. thesis, Dept. of Math., Rutgers, U., New Brunswick, 1989.