A Short Course on Graph Coloring by Hajo Broersma
(Spring School in Algorithms
Geilo, Norway, 1.-4. April 2005)
Abstract
The tutorials will cover the following aspects.
We start by motivating and introducing graph coloring, and
define the chromatic number of a graph. We study upper bounds and
lower bound for the chromatic number and heuristics for obtaining
good colorings. We also study graphs with a large chromatic number
and graphs with a small chromatic number, including planar graphs.
If time allows, we will make some excursions on variations of
classical graph coloring.