##
The Smallest Hard to Color Graphs

Marek E. Kubale
Department of Foundations of Informatics

Technical University of Gdansk

ul. Narutowicza 11/12

80-952 Gdansk, Poland

kubale@pg.gda.pl

### 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.