INTERFERENCE-MINIMIZING COLORINGS OF REGULAR GRAPHS

Communications problems that involve frequency interference, such as t he channel assignment problem in the design of cellular telephone netw orks, can be cast as graph coloring problems in which the frequencies (colors) assigned to an edge's vertices interfere if they are too simi lar. The paper considers situations modeled by vertex-coloring d-regul ar graphs with n vertices using a color set {1,2,...,n}, where colors i and j are said to interfere if their circular distance min {\i-j\,n- \i-j\} does not exceed a given threshold value alpha. Given a d-regula r graph G and threshold alpha, an interference-minimizing coloring is a coloring of vertices that minimizes the number of edges that interfe re. Let I-alpha(G) denote the minimum number of interfering edges in s uch a coloring of G. For most triples (n,alpha,d), we determine the mi nimum value of I-alpha(G) over all d-regular graphs and find graphs th at attain it. In determining when this minimum value is 0, we prove th at for r greater than or equal to 3 there exists a d-regular graph G o n n vertices that is r-colorable whenever d less than or equal to (1-1 /r)n-1 and nd is even. We also study the maximum value of I-alpha(G) o ver all d-regular graphs and find graphs that attain this maximum in m any cases.