"Записки научных семинаров ПОМИ"

Том 391, стр. 79-89

Division of Mathematical Sciences, Nanyang Technological University, Singapore

ngravin@gmail.com

С.-Петербургское отделение Математического института им. В.А.Стеклова РАН, Фонтанка 27, 191023 Санкт-Петербург, Россия

dvk0@yandex.ru

Аннотация:Пусть $\mathcal{H}$ -- гиперграф с максимальной степенью вершины $\Delta$, каждое гиперребро которого содержит не менее, чем $\delta$ вершин. Пусть $k=\lceil \frac{2\Delta}{\delta} \rceil$. Мы докажем, что вершины $\mathcal{H}$ можно правильным образом покрасить в $k + 1 $ цвет (то есть так, чтобы в каждом гиперребре было хотя бы две разноцветных вершины). При $k\ge3$ и $\delta\ge 3$ мы докажем, что вершины $\mathcal{H}$ можно правильным образом покрасить в $k$ цветов. Для графа $G$ положим $k=\lceil \frac{2\Delta(G)}{\delta(G)} \rceil$. В качестве следствия будет доказано существование динамической раскраски графа $G$ в $k +1$ цвет, а при $k\ge 3$ и $\delta(G)\ge 3$ -- в $k$ цветов. Библ. -- 16 назв.
Ключевые слова: гиперграф, правильная раскраска, динамическая раскраска [hypergraph, proper coloring, dynamic coloring]