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


Slightly Hard-to-Color Graphs


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