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 [82], Wood [85], Williams [84],
Matula [67], Matula, Marble and Isaacson [68],
Johnson [52][51], Grimmet and McDiarmid [46], Brélaz
[18], Leighton [64], Johri and Matula [54],
Wigderson [83], Berger and Rompel [12], and Kucera [62],.
The algorithm providing the currently best worst-case ratio (number
of colors used divided by optimal number) is due to Halldórsson
[47], 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 [26] and Johnson et. al [53]) and tabu search (Hertz and De Werra [49]). Issues related to finding an appropriate neighborhood structure for coloring graphs are described by Morgenstern and Shapiro [71].
Algorithms for finding optimal colorings have been for the most part based on implicit enumeration. See for instance Brown [21], Christofides [30][29], Corneil and Graham [32], Lawler [63], Korman [57], Brélaz [18], Peemöller [77], Kubale and Kusz [59], Kubale and Jackowski [58].
Other work has considered algorithms that find 
-colorings quickly
on average for various models of random -colorable graphs
[37][34][14][61][80][60]. The question of the best worst-case bounds
obtainable in polynomial time for -colorable graphs (fixed , typically
) is addressed in [14][13][83]. Papers on the expected
chromatic number of a ``usual'' random graph include Bollobás
[15], and Matula and Kucera [69].