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.