Again, there is a vast literature, but in this case no current survey, so we will try to be a bit more complete.
Let us first consider approximations algorithms for graph coloring. The most common technique used is that of successive augmentation. In this approach a partial coloring is found on a small number of vertices and this is extended vertex by vertex until the entire graph is colored. Examples of varients of this approach include Welsh and Powell , Wood , Williams , Matula , Matula, Marble and Isaacson , Johnson , Grimmet and McDiarmid , Brélaz , Leighton , Johri and Matula , Wigderson , Berger and Rompel , and Kucera ,. The algorithm providing the currently best worst-case ratio (number of colors used divided by optimal number) is due to Halldórsson , guaranteeing a ratio of no more than , where is the number of vertices.
More general heuristic techniques that have been tried include simulated annealing (Chams, Hertz, and De Werra  and Johnson et. al ) and tabu search (Hertz and De Werra ). Issues related to finding an appropriate neighborhood structure for coloring graphs are described by Morgenstern and Shapiro .
Algorithms for finding optimal colorings have been for the most part based on implicit enumeration. See for instance Brown , Christofides , Corneil and Graham , Lawler , Korman , Brélaz , Peemöller , Kubale and Kusz , Kubale and Jackowski .
Other work has considered algorithms that find -colorings quickly on average for various models of random -colorable graphs . The question of the best worst-case bounds obtainable in polynomial time for -colorable graphs (fixed , typically ) is addressed in . Papers on the expected chromatic number of a ``usual'' random graph include Bollobás , and Matula and Kucera .