G-90-59
Slightly Hard-to-Color Graphs
et référence BibTeX
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.
Paru en décembre 1990 , 21 pages