## 14 Feb 2003:

Maximal Independent Sets and Their Use in Colouring Algorithms

Jesper Makholm Byskov

I will talk about maximal independent sets in graphs and why they are
useful for colouring graphs. I will for all k show tight bounds on the
number of maximal independent sets of size at most k, and give
algorithms for finding all maximal independent sets of size at most k.
Then I will show how to use these algorithms to design better
algorithms for colouring graphs.

I will also discuss a generalisation of maximal independent sets,
namely maximal k-colourable subgraphs and give some upper and lower
bounds on the number of these.

Part of the talk is based on my SODA paper: "Algorithms for k-Colouring
and Finding Maximal Independent Sets".