Понедельник, 19 ноября, комната 203. Начало в 15:00.
Докладчик: Н. В. Гравин.
Тема: Невырожденные раскраски в теореме Брукса.
Пусть даны натуральные числа и
. Правильная раскраска вершин графа
называется
-невырожденной, если для любой вершины графа
степени хотя бы
среди смежных с ней найдутся вершины хотя бы
различных цветов.
В нашей работе мы докажем следующий результат, обобщающий широко известную теорему Брукса. Пусть , дан граф
без клик на
вершине такой, что степень любой его вершины не превосходит
. Тогда для любого
существует правильная
-невырожденная раскраска вершин графа
в
цветов, где
.
В ходе доказательства основного результата будут получены несколько интересных следствий.