The Smallest Hard to Color Graphs

ABSTRACT

Let A(G) be the number of colors used by algorithm A to color the vertices of graph G. A graph G is said to be hard-to-color (HC) (resp. slightly HC) if for every (resp. some) implementation of the algorithm A we have A(G) > ch(G), where ch(G) is the chromatic number of G. For a collection of such algorithms graph G is called a benchmark, if it is HC for every algorithm in the collection. The study of HC graphs makes it possible to design improved algorithms trying to avoid hard instances as far as possible. Hard-to-color graphs are also good benchmarks for the evaluation of existing and future algorithms and provide an alternative way of assessing their quality. In this talk we demonstrate the smallest HC graphs for the best known coloring heuristics in classical applications, as well as when adapted to the chromatic sum coloring and strong coloring of vertices. In addition, we give two collective benchmarks for sequential coloring algorithms.

Colloquia Series page.