Laboratory of Mathematical Logic

Пятница, 23 ноября, комната 203. Начало в 17:45.

Докладчик: Д. В. Карпов.

Тема: Аналог теоремы Брукса для динамических раскрасок.

Abstract

Назовем подразбиением полного графа

любой граф, который можно получить заменой нескольких ребер графа

на цепочки длины 2 (с каждой такой цепочкой добавляется новая вершина степени 2).

Назовем раскраску вершин графа

динамической, если раскраска является правильной (т.е. смежные вершины покрашены в разные цвета) и для любой вершины

графа

степени не менее 2 в окрестности

есть вершины не менее, чем двух цветов.

Пусть

--- связный простой граф с максимальной степенью вершин

. В работе доказывается, что динамическая правильная раскраска вершин графа

в

цветов существует тогда и только тогда, когда

отличен от

и его подразбиений.