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

ПРЕПРИНТ 07/2010

ЗАМЕТКА О ПРАВИЛЬНЫХ РАСКРАСКАХ ГИПЕРГРАФОВ

This preprint was accepted September 2, 2010

АННОТАЦИЯ:
Пусть $\mathcal{H}$ --- гиперграф с максимальной 
степенью вершины $\Delta$, каждое гиперребро 
которого содержит не менее, чем $\delta$ вершин. 
Мы докажем, что вершины $\mathcal{H}$ можно правильным 
образом покрасить в 
$\lceil \frac{2\Delta}{\delta} + 1 \rceil$
 цветов (то есть так, чтобы в каждом гиперребре было 
хотя бы две разноцветных вершины). 
В качестве следствия будет получен результат о динамических
 раскрасках вершин графа.©

N.V. Gravin, D.V. Karpov

A NOTE ON PROPER COLORINGS OF HYPERGRAPHS

ABSTRACT:
Let $\mathcal{H}$ be a hypergraph with maximal degree $\Delta$, 
such that each hyperedge of it has at least $\delta$ vertices. 
We prove here that $\mathcal{H}$ admits a proper coloring with
 $\lceil \frac{2\Delta}{\delta} + 1 \rceil$ colors, that is in any 
hyperedge there should be at least two vertices of different colors.
 As a corollary we derive similar result about dynamic 
colorings for graphs.