Пятница, 7 мая, ауд. 106. Начало в 18:00.
Докладчик: А. Зыкова (СПбГУ).
Тема: Повторяющиеся раскраски графов.
Abstract
Раскраска вершин графа G называется t-повторяющейся, если любая
вершина G имеет не больше t смежных вершин одного цвета. Этот термин
ввели в 1997 году Molloy и Reed. Они получили точную нижнюю оценку t
при правильной t-повторяющейся раскраске графа, максимальная степень
которого не превосходит d, в d + 1 цвет. Отсюда возникает несколько
естественных вопросов. Например, сколько цветов необходимо
использовать для того, чтобы количество повторений стало константой. А
также чему будет равно количество повторений, если использовать
меньшее количество цветов. Например, в случае k-индуктивного графа или
графа с большим обхватом. В докладе будет рассказано о таких оценках,
некоторые из которых точные.
