Further Results on T-Coloring and Frequency Assignment Problems
Arundhati Raychaudhuri · SIAM Journal on Discrete Mathematics · 1994
A graph coloring problem (called T-coloring) is investigated in which integers are assigned to the vertices of a graph G, under the constraint that the absolute value of the difference between integers assigned to adjacent vertices does not belong to a forbidden set (called the T-set). The T-coloring problem has applications in the radio frequency channel assignment problem. T-sets of the form $\{ 0,s,2s, \ldots ,ks \} \cup S$, where $s,k \geq 1$ and $S \subseteq \{ s + 1,s + 2, \ldots ,ks - 1 \}$, are considered. This set has been named the k-multiple of s set. Values of interest are the minimum cardinality, $\chi _T ( G )$, and the minimum span, $\text{sp}_{T} ( G )$, of the set of assigned integers, over all possible T-colorings of G. A greedy algorithm, which T-colors perfectly orderable graphs in $\chi _{T} ( G )$ colors with span ${\text{sp}}_T ( G )$ (for a k-multiple of s set), is given.