Семинар 19 ноября 2007 года

Понедельник, 19 ноября, комната 203. Начало в 15:00.

Докладчик: Н. В. Гравин.

Тема: Невырожденные раскраски в теореме Брукса.

Abstract

Пусть даны натуральные числа

и

. Правильная раскраска вершин графа

называется

-невырожденной, если для любой вершины графа

степени хотя бы

среди смежных с ней найдутся вершины хотя бы

различных цветов.

В нашей работе мы докажем следующий результат, обобщающий широко известную теорему Брукса. Пусть

, дан граф

без клик на

вершине такой, что степень любой его вершины не превосходит

. Тогда для любого

существует правильная

-невырожденная раскраска вершин графа

в

цветов, где

.

В ходе доказательства основного результата будут получены несколько интересных следствий.