A Pruning Procedure for Exact Graph Coloring

The graph coloring problem can be stated: “Given an undirected graph, using a minimal number of colors, assign each vertex a color so that if two vertices are connected by an edge then they are not assigned the same color.” Graph coloring can be used to solve scheduling problems with constraints of the form: events e and e\u27 can not be scheduled together. Graph coloring is an NP-Complete problem. Generally large problems are solved heuristically, although some of the better heuristic algorithms use an exact graph coloring algorithm to finish coloring a graph after first reducing it heuristically to manageable size. Exact graph coloring is important both in its own right and as a component of heuristic coloring. We present an improved exact graph coloring algorithm which runs in the mean over 20% faster than the DSATUR algorithm on some classes of random graphs. The improvement over DSATUR stems from the ability to prune the search tree by detecting in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far