Laboratory of Mathematical Logic at PDMI

Пятница, 21 ноября, комната 106. Начало в 17:55.

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

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

Abstract

Назовем подразбиением полного графа $K_n$ любой граф, который можно получить заменой нескольких ребер графа $K_n$ на цепочки длины 2 (с каждой такой цепочкой добавляется новая вершина степени 2).

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

Пусть $G$ --- связный простой граф с максимальной степенью вершин $d$ не менее $8$. В докладе будет доказано, что динамическая правильная раскраска вершин графа $G$ в $d$ цветов существует тогда и только тогда, когда $G$ отличен от $K_{d+1}$ и его подразбиений. Для доказательства фактически будет предложен алгоритм построения динамической раскраски.