Coloring

Next: Suggested Research Projects Up: Solution Approaches Previous: Cliques

Coloring

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].

Next: Suggested Research Projects Up: Solution Approaches Previous: Cliques

Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994