On the use of some known methods for \(T\)-colorings of graphs. (English) Zbl 0771.68089

Summary: A generalization of the classical graph coloring model is studied in this paper. The problem we are interested in is a variant of the general \(T\)- coloring problem related in the literature. We want to color the vertices of a graph in such a way that the two colors assigned to two adjacent vertices \(i\) and \(j\) differ by at least \(t_{ij}\), where \(t_{ij}\) is a fixed coefficient associated to the edge \([i,j]\). The goal is to minimize the length of the spectrum of colors used. We present here the results produced by well-known heuristics ( tabu search and simulated annealing) applied to the considered problem. The results are compared with optimal colorings obtained by a branch-and-bound algorithm.


68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] D. Abramson, Constructing school timetables using simulated annealing: sequential and parallel algorithms, Manag. Sci. 37(1991)98–113. · doi:10.1287/mnsc.37.1.98
[2] D. Brélaz, New methods to color the vertices of a graph, Commun. ACM 22(1979)251–256. · Zbl 0394.05022 · doi:10.1145/359094.359101
[3] R.E. Burkard and F. Rendl, A thermodynamically motivated simulation procedure for combinatorial optimization problems, Eur. J. Oper. Res. 17(1984)169–174. · Zbl 0541.90070 · doi:10.1016/0377-2217(84)90231-5
[4] M. Cangalovic and J. Schreuder, Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths, Eur. J. Oper. Res. 51(1991)248–258. · Zbl 0747.90098 · doi:10.1016/0377-2217(91)90254-S
[5] M. Chams, A. Hertz and D. de Werra, Some experiments with simulated annealing for coloring graphs, Eur. J. Oper. Res. 32(1987)260–266. · Zbl 0626.90067 · doi:10.1016/S0377-2217(87)80148-0
[6] D. Costa, A tabu search algorithm for computing an operational timetable, Eur. J. Oper. Res. (1993), to appear. · Zbl 0809.90075
[7] M. Cozzens and F.S. Roberts,T-colorings of graphs and the channel assignment problem, Congr. Numer. 35(1982)191–208.
[8] M. Cozzens and D. Wang, The general channel assignment problem, Congr. Numer. 41(1984)115–129.
[9] D. de Werra and A. Hertz, Consecutive colorings of graphs, Zeits. Oper. Res. 32(1988)1–8. · Zbl 0633.05027 · doi:10.1007/BF01920567
[10] D. de Werra and A. Hertz, Tabu search techniques: a tutorial and an application to neural networks, OR Spektrum 11(1989)131–141. · Zbl 0672.90089 · doi:10.1007/BF01720782
[11] D. de Werra and Y. Gay, Chromatic scheduling and frequency assignment, Discr. Appl. Math. (1993), to appear. · Zbl 0801.90067
[12] D. Dubois and D. de Werra, EPCOT: an efficient procedure for coloring optimally with tabu search, to appear in Comput. Math. Appl. · Zbl 0798.68128
[13] F. Glover, Tabu search Part I, ORSA J. Comput. 1(1989)190–206.
[14] F. Glover, Tabu search Part II, ORSA J. Comput. 2(1990)4–32.
[15] W.K. Hale, Frequency assignment: Theory and applications, Proc. IEEE 68(1980)1497–1514. · doi:10.1109/PROC.1980.11899
[16] A. Hertz and D. de Werra, Using search techniques for graph coloring, Computing 39(1987)345–351. · Zbl 0626.68051 · doi:10.1007/BF02239976
[17] A. Hertz and D. de Werra, The tabu search metaheuristic: how we used it, Ann. Math. Art. Int. 1(1990)111–121. · Zbl 0878.68053 · doi:10.1007/BF01531073
[18] M. Kubale and B. Jackowski, A generalized implicit enumeration algorithm for graph coloring, Commun. ACM 28(1985)412–418. · doi:10.1145/3341.3350
[19] J. Peemöller, A correction to Brélaz’s modification of Brown’s coloring algorithm, Commun. ACM 26(1983)595–597. · doi:10.1145/358161.358171
[20] A. Raychaudhuri, Intersection assignments,T-coloring and powers of graphs, Ph.D. Thesis, Rutgers University (1985).
[21] F.S. Roberts, From garbage to rainbows: generalizations of graph coloring and their applications, RUTCOR Research Report 36-88, Rutgers University (1988).
[22] F. Semet and E. Taillard, Solving real-life vehicle routing problems efficiently using taboo search, Ann. Oper. Res. (1993), this volume. · Zbl 0775.90156
[23] B.A. Tesman,T-colorings, listT-colorings and setT-colorings of graphs, Ph.D. Thesis, Rutgers University (1989).
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.