Home

Семинар 21 ноября 2008 года

Пятница, 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} $ и его подразбиений. Для доказательства фактически будет предложен алгоритм построения динамической раскраски.