Chromatic scheduling and frequency assignment. (English) Zbl 0801.90067

Summary: Some extensions of classical coloring models are developed; these consist in assigning to each node a set of consecutive colors; furthermore for each oriented arc \((i,j)\) in a graph a set \(T_{ij}\) of consecutive integers is given. It is required to find an assignment of colors to the nodes such that for each arc \((i,j)\) the first colors \(f(i)\), \(f(j)\) given to nodes \(i\) and \(j\) satisfying \(f(j)- f(i)\not\in T_{ij}\). This model can be used for assigning frequencies to a collection of stations as well as for chromatic scheduling problems. Simple upper bounds on the generalized chromatic number are derived. Computational results are reported for some randomly generated problems.


90B35 Deterministic scheduling theory in operations research
05C15 Coloring of graphs and hypergraphs
90B30 Production models
Full Text: DOI


[1] Berge, C., Graphes (1983), Gauthier-Villars: Gauthier-Villars Paris · Zbl 0213.25702
[2] Brélaz, D., New methods to color the vertices of a graph, Comm. ACM, 22, 251-256 (1979) · Zbl 0394.05022
[3] Cozzens, M.; Roberts, F. S., \(T\)-colorings of graphs and the channel assignment problem, Congr. Numer., 35, 191-208 (1982) · Zbl 0537.05023
[4] de Werra, D., An introduction to timetabling, European J. Oper. Res., 19, 151-162 (1985) · Zbl 0553.90059
[5] de Werra, D.; Hertz, A., Consecutive colorings of graphs, Z. Oper. Res., 32, 1-8 (1988) · Zbl 0633.05027
[6] Gay, Y., Affectation de fréquences à des émetteurs de l’OTAN, (diploma thesis (1988), Swiss Federal Institute of Technology: Swiss Federal Institute of Technology Lausanne)
[7] Hale, W. K., Frequency assignment: Theory and applications, Proc. IEEE, 68, 1497-1514 (1980)
[8] Hansen, P.; Delattre, M., Complete-link cluster analysis by graph coloring, J. Amer. Statist. Assoc., 73, 397-403 (1978) · Zbl 0432.05004
[9] Hertz, A.; de Werra, D., Using Tabu search techniques for graph coloring, Computing, 39, 345-351 (1987) · Zbl 0626.68051
[10] Lanfear, T. A., A frequency assignment scenario, NATO Report (1988)
[11] Randall Brown, J., Chromatic scheduling and the chromatic number problem, Management Sci., 18, 456-463 (1972) · Zbl 0247.90028
[12] Roberts, F. S., From garbage to rainbows: Generalizations of graph coloring and their applications, (RUTCOR Res. Rept. 36-88 (1988), Rutgers University: Rutgers University New Brunswick, NJ) · Zbl 0841.05033
[13] Smith, D., Graph coloring and frequency assignment, Ars Combin., 25, 205-212 (1988) · Zbl 0653.05032
[14] Szekeres, G.; Wilf, H., An inequality for the chromatic number of a graph, J. Combin. Theory, 4, 1-3 (1968) · Zbl 0171.44901
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.