Home

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

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

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

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

Abstract

Пусть даны натуральные числа $ c>=2 $ и $ p>=c $. Правильная раскраска вершин графа $ G $ называется $ (c,p) $-невырожденной, если для любой вершины графа $ G $ степени хотя бы $ p $ среди смежных с ней найдутся вершины хотя бы $ c $ различных цветов.

В нашей работе мы докажем следующий результат, обобщающий широко известную теорему Брукса. Пусть $ D>=3 $, дан граф $ G $ без клик на $ D+1 $ вершине такой, что степень любой его вершины не превосходит $ D $. Тогда для любого $ c>=2 $ существует правильная $ (c,p) $-невырожденная раскраска вершин графа $ G $ в $ D $ цветов, где $ p=(c^3+8c^2+19c+6)(c-1) $.

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