Число независимости и хроматическое число возникают во многих задачах теории графов. С ними связано много труднейших задач и гипотез (теорема о четырёх красках, задача о хроматическом числе плоского графа, все рёбра которого имеют длину 1 и др.)

Известно, что число независимости и хроматическое число дружат со степенями вершин графа и числом его рёбер, красивые точные оценки дают, например, теорема Турана и теорема Брукса.

Программа спецкурса:

1. Теорема Турана как серия линейных оценок на число вершин n, число рёбер m и число независимости а графа. Множество возможных графов в координатах, его выпуклость. Подход через удаление вершины с соседями для доказательства линейных оценок

2. Оценки хроматического числа через число независимости и максимальную степень вершины. Теорема Брукса