Эта публикация цитируется в
11 статьях
О существовании полноцветных раскрасок для равномерных гиперграфов
Д. А. Шабанов Механико-математический факультет
Московского государственного университета им. М. В. Ломоносова
Аннотация:
Рассматривается известная экстремальная задача о полноцветных раскрасках гиперграфов. Раскраска в
$r$ цветов множества вершин гиперграфа называется полноцветной, если в ней каждое ребро содержит вершины всех цветов. Изучается величина
$p(n,r)$, равная минимально возможному количеству ребер в
$n$-равномерном гиперграфе, для которого не существует полноцветной
$r$-раскраски. Получены новые нижние и верхние оценки величины
$p(n,r)$, улучшающие предыдущие результаты
при многих соотношениях между параметрами
$n$ и
$r$. Кроме того, получено достаточное условие существования полноцветной
$r$-раскраски у
$n$-равномерного гиперграфа.
Библиография: 18 названий.
Ключевые слова:
гиперграф, полноцветная раскраска, метод случайной раскраски.
УДК:
519.112.7+
519.179.1
MSC: Primary
05C15; Secondary
05C65 Поступила в редакцию: 05.11.2008
DOI:
10.4213/sm7480