×

\(T\)-graphs and the channel assignment problem. (English) Zbl 0870.05023

Summary: \(T\)-colorings arose form 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 \(\text{sp}_T(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: \({\mathcal G}=\{T:\) greedy (or first-fit) algorithm provides \(T\)-spans for all complete graphs}, and \({\mathcal E}=\{T:\text{sp}_T(G)=\text{sp}_T(K_{\chi(G)})\) for all graphs \(G\), where \(\chi\) 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\in\mathbb{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\in\mathbb{Z}^+\), \(T\in{\mathcal E}\) if and only if \(aT\in{\mathcal E}\), and \(T\in{\mathcal G}\) if and only if \(aT\in{\mathcal G}\). The second fact has been proven by M. B. Cozzens and F. S. Roberts [J. Comb. Inf. Syst. Sci. 16, No. 4, 286-299 (1991; Zbl 0774.05037)] from a different approach. We will completely solve the family of sets \(T=\{0,s,s+1,\dots,l\}\) by providing a different proof of the fact \(T\in{\mathcal G}\) (B. A. Tesman, Ph.D. Dissertation, New Brunswick, 1989), and showing that \(T\in{\mathcal 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\in\mathbb{Z}^+\) with \(s\leq l\), \(T=\{0,as,a(s+1),a(s+2),\dots,al\}\cup A\in{\mathcal G}\), and \(T\in{\mathcal E}\) if and only if \(l=ms\) for some \(m\), where \(A\subseteq\{as+1,as+2,\dots,al-1\}\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory

Citations:

Zbl 0774.05037
Full Text: DOI

References:

[1] Cozzens, M. B.; Roberts, F. S., \(T\)-colorings of graphs and the channel assignment problem, (Congr. Numer., 35 (1982)), 191-208 · Zbl 0537.05023
[2] Cozzens, M. B.; Roberts, F. S., Greedy algorithms for \(T\)-colorings of complete graphs and the meaningfulness of conclusions about them, J. Combin. Inform. System Sci., 16, 286-299 (1991) · Zbl 0774.05037
[3] Cozzens, M. B.; Wang, D. I., The general channel assignment problem, (Congr. Numer., 41 (1984)), 115-129 · Zbl 0548.05060
[4] Griggs, J. R.; Liu, D. D.-F., The channel assignment problem for mutually adjacent sites, J. Combin. Theory, Ser. A, 68, 169-183 (1994) · Zbl 0816.05027
[5] Hale, W. K., Frequency assignment: theory and applications, (Proc. IEEE, 68 (1980)), 1497-1514
[6] Liu, D. D.-F., \(T\)-colorings of graphs, Discrete Math., 101, 203-212 (1992) · Zbl 0779.05021
[7] Liu, D. D.-F., Graph homomorphisms and the channel assignment problem, (Ph.D. Dissertation (1991), Department of Mathematics, University of South Carolina: Department of Mathematics, University of South Carolina Columbia, SC)
[8] Liu, D. D.-F., On a conjecture of \(T\)-colorings, (Congr. Numer., 103 (1994)), 27-31 · Zbl 0836.05033
[9] Rabinowitz, J. H.; Proulx, V. K., An asymptotic approach to the channel assignment problem, SIAM J. Algebraic Discrete Methods, 6, 507-518 (1995) · Zbl 0579.05058
[10] Raychaudhuri, A., Intersection assignment, \(T\)-colorings, and powers of graphs, (Ph.D. Dissertation (1985), Department of Mathematics, Rutgers University: Department of Mathematics, Rutgers University New Brunswick, NJ)
[11] A. Raychaudhuri, Further results on \(T\); A. Raychaudhuri, Further results on \(T\) · Zbl 0810.05026
[12] Roberts, F. S., \(T\)-colorings of graphs: recent results and open problems, Discrete Math., 93, 229-245 (1991) · Zbl 0751.05042
[13] Tesman, B. A., \(T\)-colorings, list \(T\)-colorings, and set \(T\)-colorings of graphs, (Ph.D. Dissertation (1989), Department of Mathematics, Rutgers University: Department of Mathematics, Rutgers University New Brunswick, NJ) · Zbl 0788.05047
[14] Wang, D.-I., The Channel assignment problem and closed neighborhood containment graphs, (Ph.D. Dissertation (1985), Northeastern University: Northeastern University Boston, MA)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.