Home

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

Вторник, 30 декабря, комната 106. Начало в 14:55.

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

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

Abstract

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

Ошибка, найденная в предыдущей попытке доложить результат, исправлена! Доклад будет начат сначала.