Back

G-2006-16

On Edge Orienting Methods for Graph Coloring

, , and

BibTeX reference

We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy and Vitaver, this edge orienting problem is equivalent to finding the chromatic number of a graph. We study various properties of edge orienting methods in the context of local search for graph coloring. We then exploit these properties to derive four tabu search algorithms, each based on a different neighborhood. We compare these algorithms numerically to determine which are the most promising and to give potential research directions.

, 22 pages

Research Axis

Publication

On edge orienting methods for graph coloring
, , and
Journal of Combinatorial Optimization, 13(2), 163–178, 2007 BibTeX reference