T-graphs and the channel assignment problem

AbstractT-colorings arose from the channel assignment problem in communications. Given a finite set T of non-negative integers, a T-coloring of a simple graph G is an assignment of a non-negative integer (channel) on every vertex of G, such that the difference of channels of two adjacent vertices does not fall in T. The T-span of G, denoted by spT(G), is the minimum span among all possible T-colorings of G, where the span of a T-coloring is the difference between the largest and smallest channels used. This article applies T-graphs to explore the sets T that belong to these two collections: G = {T : greedy (or first-fit) algorithm provides T-spans for all complete graphs}, and E = {T : spt(G) = spT(Kχ(G)) for all graphs G, where χ is the chromatic number}. Given T, its T-graph has the vertex set of all non-negative integers so that two vertices are adjacent if their difference does not fall in T. We show that for any a ∈ Z+, the T-graph of aT is isomorphic to a disjoint product of a copies of the T-graph of T, where aT is the set obtained by multiplying every element of T by a. Based on this characterization, the following two results are attained. For any a ∈ Z+, T ∈E if and only if aT ∈ E, and T ∈ G if and only if aT ∈ G. The second fact has been proven by Cozzens and Roberts (1991) from a different approach. We will completely solve the family of sets T = {0, s,s + 1,…, l } by providing a different proof of the fact T ∈ G (Tesman, 1989), and showing that T ∈ E if and only if l is a multiple of s. In addition, complete solutions for a more general family are obtained: for any a, s, l ∈ Z+ with s ⩽ l, T = {0, as, a(s + 1), a(s + 2),…, al} ∪ A ∈ E, and T ϵ E if and only if l = ms for some m , where A ⊆{as + 1, as + 2, …, al - 1}