ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2013, ТОМ 18, ВЫПУСК 3, СТР. 77-115

Раскраски частичных систем Штейнера и их приложения

А. Б. Купавский
Д. А. Шабанов

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

В работе рассматриваются экстремальные задачи о раскрасках частичных систем Штейнера. Получено новое достаточное условие $r$-раскрашиваемости для некоторого класса подобных систем в терминах ограничения на максимальную степень вершины. Кроме того, в качестве следствия получена новая нижняя оценка для пороговой вероятности $r$-раскрашиваемости случайного гиперграфа в биномиальной модели.

Полнотекстовая версия статьи в формате PDF (345 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k13/k133/k13307h.htm
Изменения вносились 4 марта 2014 г.