[85]S. Khanna, N Linial, and S Safra, On the hardness of approximating the chromatic number, Proc. 2nd Israel Symp. on Theory of Computing and Systems, IEEE Computer Society,(1993), 250-26C 86] C. Lund, and M. Yannakakis, On the hardness of approximating minimization problems, J ACM41(1994),960-981 [87]M. V. Marathe, H. Breu, H. B. Hunt Ill, S.S. Ravi, and D J. Rosenkrantz, Simple heuristics for unit disk graphs, Networks, 25(1995), 59-68 [88]A. Blum, New Approximation algorithms for graph coloring, Journal of the ACM, 41(1994), 470-516 1891 A. Blum. Some tools for approximate 3-coloring. In Proceedings 3Ist IEEE Symposium on Foundations of Computer Science, pages 554-562, Los Angeles, CA, 1990. IEEE Computer 190] M. Laguna and R. Marti, A GRASP for coloring sparse graphs. Computational optimization and applications, 19(2)(2001), 165-178 91] Alon N, Krivelevich M, and Sudakov B, Coloring graphs with sparse neighborhoods Journal of Combinatorial Theory, Ser. B, 77(1999), 73-82 [92 Morgenstern C. and Shapiro H., Coloration neighborhood structures for general graph coloring. In Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms (1990), 226-235. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA 93] Avanthay C, Hertz A, and Zufferey N, a variable neighborhood search for graph coloring European journal of Operational Research, (2003) 94] Glass C.A. and Prugel-Bennett A, A polynomially searchable exponential neighbourhood for graph colouring. Journal ofthe Operational Research Society, 56(3)(2005), pp. 324-330 95] Hertz A and de Werra D, Using tabu search techniques for graph coloring. Computing, 39(4) (1987),345-351 96]Gonzalez-Velarde J and Laguna M, Tabu search with simple ejection chains for coloring graphs. Annals of Operations Research, 117(1-4)(2002), 165-174 [97] Chiarandini M. and Stutzle T, An application of iterated local search to graph coloring. In Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, edited by D.s. Johnson, A Mehrotra, and M. Trick, (2002), 112-125. Ithaca, New York, USA [98 Fleurent C and Ferland J, Object-oriented implementation of heuristics search methods for graph coloring, maximum clique, and satisfiability. vol 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996),619-652, American Mathematical Society, Providence, RI, USA 99]D de Werra, Lausanne, Heuristics for graph coloring. Computing Supplementum, 7(1990) 91-208 [100] Blas A D, Jagota A, and Hughey R, A range-compaction heuristic for graph coloring Journal of Heuristics, 9(3)(2003), 489-506 [101] Lewandowski G. and Condon A, Experiments with parallel graph coloring heuristics and applications of graph coloring. vol 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996), 309-334. American Mathematical Society, Providence, RI USA8 [85] S. Khanna, N.Linial, and S. Safra, On the hardness of approximating the chromatic number, Proc. 2nd Israel Symp. on Theory of Computing and Systems, IEEE Computer Society, (1993), 250-260. [86] C. Lund, and M. Yannakakis, On the hardness of approximating minimization problems, J. ACM 41(1994), 960-981. [87] M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, and D. J. Rosenkrantz, Simple heuristics for unit disk graphs, Networks，25(1995), 59-68. [88] A. Blum, New Appproximation algorithms for graph coloring, Journal of the ACM, 41(1994), 470-516. [89] A. Blum. Some tools for approximate 3-coloring. In Proceedings 31st IEEE Symposium on Foundations of Computer Science, pages 554-562, Los Angeles, CA, 1990. IEEE Computer Society. [90] M. Laguna and R. Martí, A GRASP for coloring sparse graphs. Computational optimization and applications, 19(2) (2001), 165-178. [91] Alon N., Krivelevich M., and Sudakov B. , Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Ser. B, 77(1999), 73-82. [92] Morgenstern C. and Shapiro H. , Coloration neighborhood structures for general graph coloring. In Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms, (1990), 226-235. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. [93] Avanthay C., Hertz A., and Zufferey N. , A variable neighborhood search for graph coloring. European Journal of Operational Research, (2003). [94] Glass C.A. and Prügel-Bennett A. , A polynomially searchable exponential neighbourhood for graph colouring. Journal of the Operational Research Society, 56(3) (2005), pp. 324-330. [95] Hertz A. and de Werra D., Using tabu search techniques for graph coloring. Computing, 39(4) (1987), 345-351. [96] González-Velarde J. and Laguna M., Tabu search with simple ejection chains for coloring graphs. Annals of Operations Research, 117(1-4) (2002), 165-174. [97] Chiarandini M. and Stützle T. , An application of iterated local search to graph coloring. In Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, edited by D.S. Johnson, A. Mehrotra, and M. Trick, (2002), 112-125. Ithaca, New York, USA. [98] Fleurent C. and Ferland J. , Object-oriented implementation of heuristics search methods for graph coloring, maximum clique, and satisfiability. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996), 619-652, American Mathematical Society, Providence, RI, USA. [99] D. de Werra, Lausanne, Heuristics for graph coloring. Computing Supplementum, 7(1990) 191-208. [100] Blas A.D., Jagota A., and Hughey R. , A range-compaction heuristic for graph coloring. Journal of Heuristics, 9(3) (2003), 489-506. [101] Lewandowski G. and Condon A., Experiments with parallel graph coloring heuristics and applications of graph coloring. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996), 309-334. American Mathematical Society, Providence, RI, USA