|
Записки научных семинаров ПОМИ, 2011, том 391, страницы 79–89
(Mi znsl4569)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О правильных раскрасках гиперграфов
Н. В. Гравинa, Д. В. Карповb a Division of Mathematical Sciences, Nanyang Technological University, Singapore
b С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия
Аннотация:
Пусть $\mathcal H$ – гиперграф с максимальной степенью вершины $\Delta$, каждое гиперребро которого содержит не менее, чем $\delta$ вершин. Пусть $k=\lceil\frac{2\Delta}\delta\rceil$. Мы докажем, что вершины $\mathcal H$ можно правильным образом покрасить в $k+1$ цвет (то есть так, чтобы в каждом гиперребре было хотя бы две разноцветных вершины). При $k\ge3$ и $\delta\ge3$ мы докажем, что вершины $\mathcal H$ можно правильным образом покрасить в $k$ цветов.
Для графа $G$ положим $k=\lceil\frac{2\Delta(G)}{\delta(G)}\rceil$. В качестве следствия будет доказано существование динамической раскраски графа $G$ в $k+1$ цвет, а при $k\ge3$ и $\delta(G)\ge3$ – в $k$ цветов.
Библ. – 16 назв.
Ключевые слова:
гиперграф, правильная раскраска, динамическая раскраска.
Поступило: 18.10.2011
Образец цитирования:
Н. В. Гравин, Д. В. Карпов, “О правильных раскрасках гиперграфов”, Комбинаторика и теория графов. III, Зап. научн. сем. ПОМИ, 391, ПОМИ, СПб., 2011, 79–89; J. Math. Sci. (N. Y.), 184:5 (2012), 595–600
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl4569 https://www.mathnet.ru/rus/znsl/v391/p79
|
Статистика просмотров: |
Страница аннотации: | 242 | PDF полного текста: | 85 | Список литературы: | 41 |
|