Groupe d’études et de recherche en analyse des décisions

G-90-59

Slightly Hard-to-Color Graphs

et

A graph is said to be slightly hard to color for a given vertex-coloring heuristic if some implementation of the algorithm uses more colors than are necessary. We study small slightly hard-to-color graphs for various known heuristics, present implementations, and report on an exhaustive search of these graphs done on the computer.

, 21 pages