Хроматические числа графов, жадные алгоритмы раскраски и их уточнения

В лекции мы расскажем о хроматических числах графов, т.е. об экстремальных характеристиках графов, равных наименьшему количеству цветов, в которые можно так раскрасить вершины графов, чтобы между вершинами одного цвета не было ребер. Сперва речь пойдет о жадных раскрасках, и пафос будет в том, что даже они дают в определенном смысле весьма точные результаты. Затем мы поговорим об уточнениях жадных раскрасок. А под конец поговорим о раскрасках случайных подграфов в некоторых последовательностях графов.

Страница лекции на сайте Computer Science клуба