\(T\)-colorings of graphs: recent results and open problems. (English) Zbl 0751.05042

Roberts, Fred S.

Discrete Math. 93, No. 2-3, 229-245 (1991).

Author’s abstract: “Suppose \(G\) is a graph and \(T\) is a set of nonnegative integers. A \(T\)-coloring of \(G\) is an assignment of a positive integer \(f(x)\) to each vertex \(x\) of \(G\) so that if \(x\) and \(y\) are joined by an edge of \(G\), then \(| f(x)-f(y)|\) is not in \(T\). \(T\)-colorings were introduce by Hale in connection with the channel assignment problem in communications. Here, the vertices of \(G\) are transmitters, an edge represents interference, \(f(x)\) is a television or radio channel assigned to \(x\), and \(T\) is a set of disallowed separations for channels assigned to interfering transmitters. One seeks to find a \(T\)-coloring which minimizes either the number of different channels \(f(x)\) used or the distance between the smallest and largest channel. This paper surveys the results and mentions open problems concerned with \(T\)-colorings and their variations and generalizations.”
After some general results in Section 2, results under special assumptions about the set \(T\) are presented in Section 3 and about the graph \(G\) in Section 4. In subsequent sections other aspects of the \(T\)- coloring problem are discussed, namely edge span, optimal \(T\)-colorings under restrictions on order or span, channel assignments when there are several levels of interference, set \(T\)-colorings, list \(T\)-colorings, and no-hole \(T\)-colorings.

Reviewer: I.Tomescu (Bucureşti)

MSC:

05C15	Coloring of graphs and hypergraphs
05C90	Applications of graph theory

Keywords:

\(T\)-colorings of graphs; channel assignment problem; interference graph; \(T\)-chromatic number; \(\gamma\)-perfect graph; greedy algorithm; chordal graph

References:

[1]	Baybars, I., Optimal assignment of broadcasting frequencies, European J. Oper. Res., 9, 257-263 (1982) · Zbl 0475.90091
[2]	Berry, L. A.; Cronin, D. H., Spectrum-efficient frequency assignment in mixed service bands, Proceedings of the IEEE International Symposium on Electromagnetic Compatibility Record, 7-10 (1982)
[3]	Berry, L. A.; Cronin, D. H., The spectrum cost of frequency-distance separation rules, Proceedings of the IEEE International Symposium on Electromagnetic Compatibility Record, 75-78 (1983)
[4]	Bloom, G. S.; Golomb, S., Applications of numbered, undirected graphs, Proc. IEEE, 65, 562-570 (1977)
[5]	Bloom, G. S.; Golomb, S., Numbered complete graphs, unusual rulers, and assorted applications, (Alavi, Y.; Lick, D. R., Theory and Applications of Graphs (1978), Springer: Springer Berlin), 53-65 · Zbl 0426.05049
[6]	Boesch, F. T.; Chen, S.; McHugh, J. A.M., On covering the points of a graph with point disjoint paths, (Bari, R.; Harary, F., Graphs and Combinatorics (1974), Springer: Springer Berlin), 201-212, Lecture Notes in Math., Number 406 · Zbl 0298.05133
[7]	Bollobás, B.; Harris, A. J., List colourings of graphs, Graphs Combin., 1, 115-127 (1985) · Zbl 0606.05027
[8]	Bonias, I., \(T\)-Colorings of complete graphs, (Ph.D. Thesis (1991), Department of Mathematics, Northeastern University: Department of Mathematics, Northeastern University Boston, MA)
[9]	Chinn, P. Z.; Chung, F. R.K.; Erdös, P.; Graham, R. L., On the bandwidths of a graph and its complement, (Chartrand, G., The Theory and Applications of Graphs (1981), Wiley: Wiley New York), 243-253 · Zbl 0467.05038
[10]	Chvátal, V., Perfectly Ordered Graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs (1984), North-Holland: North-Holland Amsterdam), 63-65 · Zbl 0559.05055
[11]	Chvatalova, J., On the bandwidth problem for graphs, (Ph.D. Dissertation (1980), Department of Mathematics, University of Waterloo: Department of Mathematics, University of Waterloo Waterloo, Ont., Canada) · Zbl 0603.05042
[12]	Cozzens, M. B.; Roberts, F. S., Double semiorders and double indifference graphs, SIAM J. Algebraic Discrete Methods, 3, 566-583 (1982) · Zbl 0519.05059
[13]	Cozzens, M. B.; Roberts, F. S., \(T\)-Colorings of graphs and the channel assignment problem, Congr. Numer., 35, 191-208 (1982)
[14]	Cozzens, M. B.; Roberts, F. S., Greedy algorithms for \(T\) -colorings of complete graphs and the meaningfulness of conclusions about them, J. Comb. Inform. Syst. Sci. (1992), to appear. · Zbl 0774.05037
[15]	Cozzens, M. B.; -I. Wang, D., The general channel assignment problem, Congr. Numer., 41, 115-129 (1984)
[16]	Doignon, J-P, Threshold representations of multiple semiorders, SIAM J. Algebraic Discrete Methods, 8, 77-84 (1987) · Zbl 0613.06002
[17]	Erdös, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, Congr. Numer., 26, 125-157 (1979)
[18]	Füredi, Z.; Griggs, J. R.; Kleitman, D. J., Pair labellings with given distance, SIAM J. Discrete Math., 2, 491-499 (1989) · Zbl 0727.05022
[19]	Gilbert, E. N., Technical Memorandum (1972), Bell Telephone Laboratories: Bell Telephone Laboratories Murray Hill, NJ, Unpublished
[20]	Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[21]	Goodman, S.; Hedetniemi, S., On the Hamiltonian completion problem, (Bari, R.; Harary, F., Graphs and Combinatorics (1974), Springer: Springer Berlin), 262-272, Lecture Notes in Math., No. 406 · Zbl 0297.05134
[22]	Grötschel, M.; Lovasz, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056
[23]	Hale, W. K., Frequency assignment: theory and applications, Proc. IEEE, 68, 1497-1514 (1980)
[24]	Hale, W. K., Frequency assignment methodology: an annotated bibliography, (National Telecommunications and Information Administration Report (1980), Institute for Telecommunication Sciences: Institute for Telecommunication Sciences Boulder, CO), NTIA-SP-80-10, N.T.I.A.
[25]	Hale, W. K., Spectrum efficiency as a function of frequency-distance rules: an application to UHF-TV, (Spectrum Utilization Division, S.U.D. Working Paper 81-30 (1981), Institute for Telecommunication Sciences: Institute for Telecommunication Sciences Boulder, CO), N.T.I.A.
[26]	Hale, W. K., New spectrum management tools, Proceedings of the IEEE International Symposium on Electromagnetic Compatibility Record, 47-53 (1981)
[27]	Havel, T., The combinatorial distance geometry approach to the calculation of molecular conformation, Congr. Numer., 35, 361-371 (1982)
[28]	Havel, T.; Kuntz, I. D.; Crippen, G. M., The combinatorial distance geometry approach to the calculation of molecular conformation I: A new approach to an old problem, J. Theor. Biol., 104, 359-381 (1983)
[29]	Havel, T.; Kuntz, I. D.; Crippen, G. M.; Blaney, J. M., The combinatorial distance geometry approach to the calculation of molecular conformation II: Sample problems and computational statistics, J. Theor. Biol., 104, 383-400 (1983)
[30]	Lanfear, T. A., A frequency assignment scenario, (Allied Radio Frequency Agency (June 1988), NATO Headquarters: NATO Headquarters Belgium), B-1110 Brussels
[31]	Lanfear, T. A., Radio frequency assignment and graph coloring, (RUTCOR (May 1988), Rutgers University: Rutgers University New Brunswick, NJ), presentation at Third Advanced Research Institute in Discrete Applied Mathematics
[32]	Liu, D. D., Graph homomorphisms and the channel assignment problem, (Ph.D. Thesis (1991), Department of Mathematics, University of South Carolina: Department of Mathematics, University of South Carolina Columbia, SC)
[33]	Maehara, H., Space graphs and sphericity, Discrete Appl. Math., 7, 55-64 (1984) · Zbl 0527.05028
[34]	Metzger, B. H., Spectrum management technique, 38th National ORSA Meeting (1970), Detroit, MI
[35]	Middendorf, M.; Pfeiffer, F., On the complexity of recognizing perfectly orderable graphs, Rep. 89594-OR (September 1989), Forschungsinstitut für Diskrete Mathematik, Universität Bonn: Forschungsinstitut für Diskrete Mathematik, Universität Bonn Bonn, Germany
[36]	Middlekamp, L. C., UHF taboos—history and development, IEEE Trans. Consumer Electron, CE-24, 514-519 (1978)
[37]	Opsut, R. J.; Roberts, F. S., On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems, (Chartrand, G.; Alavi, Y.; Goldsmith, D. L.; Lesniak-Foster, L.; Lick, D. R., The Theory and Applications of Graphs (1981), Wiley: Wiley New York), 479-492 · Zbl 0471.05032
[38]	Pugh, G. E.; Lucas, G. L.; Krupp, J. C., Optimal allocation of TV channels—a feasibility study, (Tech. Rep. DSA No. 261 (August 1981), Decision-Science Applications, Inc: Decision-Science Applications, Inc Arlington, VA)
[39]	Rabinowitz, J. H.; Proulx, V. K., An asymptotic approach to the channel assignment problem, SIAM J. Algebraic Discrete Methods, 6, 507-518 (1985) · Zbl 0579.05058
[40]	Raychaudhuri, A., Intersection assignments, \(T\) -coloring, and powers of graphs, (Ph.D. Thesis (1985), Department of Mathematics, Rutgers University: Department of Mathematics, Rutgers University New Brunswick, NJ)
[42]	Roberts, F. S., Graph theory and its applications to problems of society, (CBMS-NSF Monograph No. 29 (1978), SIAM: SIAM Philadelphia) · Zbl 0193.24301
[43]	Roberts, F. S., On the mobile radio frequency assignment problem and the traffic light phasing problem, Ann. New York Acad. Sci., 319, 466-483 (1979)
[44]	Roberts, F. S., From garbage to rainbows: generalizations of graph colorings and their applications, (Alavi, Y.; Chartrand, G.; Oellermann, O. R.; Schwenk, A. J., Graph Theory, Combinatorics, and Applications, Vol. 2 (1991), Wiley: Wiley New York), 1031-1052 · Zbl 0841.05033
[47]	Smith, D. H., Graph colouring and frequency assignment, Ars Combin., 25C, 205-212 (1988) · Zbl 0653.05032
[48]	Stahl, S., n-tuple colorings and associated graphs, J. Combin. Theory, 20, 185-203 (1976) · Zbl 0293.05115
[49]	Tesman, B., \(T\)-colorings, list \(T\)-colorings, and set \(T\)-colorings of graphs, (Ph.D. Thesis (October 1989), Department of Mathematics, Rutgers University: Department of Mathematics, Rutgers University New Brunswick, NJ) · Zbl 0788.05047
[50]	Tesman, B., Applications of forbidden difference graphs to \(T\) -coloring, Congr. Numer., 74, 15-24 (1990)
[51]	Tesman, B., Set \(T\)-colorings, Congr. Numer., 77, 229-242 (1990) · Zbl 0862.05042
[52]	Wang, D.-I., The channel assignment problem and closed neighborhood containment graphs, (Ph.D. Thesis (1985), Northeastern University: Northeastern University Boston, MA)
[53]	Zoellner, J. A., Frequency assignment games and strategies, IEEE Trans. on Electromag. Compatibility, EMC-15, 191-196 (1973)
[54]	Zoellner, J. A.; Beall, C. L., A breakthrough in spectrum conserving frequency assignment technology, IEEE Trans. on Electromag. Compatibility, EMC-19, 313-319 (1977)