Laboratory of Mathematical Logic at PDMI

Понедельник, 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)$.

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