|
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)
О существовании полноцветных раскрасок для равномерных гиперграфов
Д. А. Шабанов Механико-математический факультет
Московского государственного университета им. М. В. Ломоносова
Аннотация:
Рассматривается известная экстремальная задача о полноцветных раскрасках гиперграфов. Раскраска в $r$ цветов множества вершин гиперграфа называется полноцветной, если в ней каждое ребро содержит вершины всех цветов. Изучается величина $p(n,r)$, равная минимально возможному количеству ребер в $n$-равномерном гиперграфе, для которого не существует полноцветной $r$-раскраски. Получены новые нижние и верхние оценки величины $p(n,r)$, улучшающие предыдущие результаты
при многих соотношениях между параметрами $n$ и $r$. Кроме того, получено достаточное условие существования полноцветной $r$-раскраски у $n$-равномерного гиперграфа.
Библиография: 18 названий.
Ключевые слова:
гиперграф, полноцветная раскраска, метод случайной раскраски.
Поступила в редакцию: 05.11.2008
Образец цитирования:
Д. А. Шабанов, “О существовании полноцветных раскрасок для равномерных гиперграфов”, Матем. сб., 201:4 (2010), 137–160; D. A. Shabanov, “The existence of panchromatic colourings for uniform hypergraphs”, Sb. Math., 201:4 (2010), 607–630
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm7480https://doi.org/10.4213/sm7480 https://www.mathnet.ru/rus/sm/v201/i4/p137
|
Статистика просмотров: |
Страница аннотации: | 681 | PDF русской версии: | 249 | PDF английской версии: | 25 | Список литературы: | 69 | Первая страница: | 9 |
|