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