|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О правильных раскрасках гиперграфов в предписанные цвета
А. П. Розовская, Д. А. Шабанов
Аннотация:
Рассматривается обобщение классической задачи Эрдеша–Хайнала в теории гиперграфов на случай предписанных раскрасок. Изучается величина $m_{pr}(n,r)$, равная минимальному числу ребер гиперграфа в классе $n$-равномерных гиперграфов, предписанное хроматическое число которых больше $r$. Получена нижняя оценка данной величины, которая улучшает ранее известные результаты для $r\ge3$. Кроме того, указано достаточное условие существования предписанной $r$-раскрашиваемости $n$-равномерного гиперграфа в терминах ограничений на пересечение ребер. В качестве следствия получена новая нижняя оценка величины $m_{pr}^*(n,r)$, равной минимальному числу ребер гиперграфа в классе $n$-равномерных простых гиперграфов (в которых любые два ребра имеют не более одной общей вершины), предписанное хроматическое число которых больше $r$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 06–01–00383, и программы Президента Российской Федерации поддержки ведущих научных школ, грант НШ 691.2008.1.
Статья поступила: 19.12.2008
Образец цитирования:
А. П. Розовская, Д. А. Шабанов, “О правильных раскрасках гиперграфов в предписанные цвета”, Дискрет. матем., 22:3 (2010), 94–109; Discrete Math. Appl., 20:4 (2010), 391–409
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1110https://doi.org/10.4213/dm1110 https://www.mathnet.ru/rus/dm/v22/i3/p94
|
Статистика просмотров: |
Страница аннотации: | 595 | PDF полного текста: | 187 | Список литературы: | 59 | Первая страница: | 12 |
|