RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2011 Volume 391, Pages 79–89 (Mi znsl4569)

This article is cited in 1 paper

On proper colorings of hypergraphs

N. V. Gravina, D. V. Karpovb

a Division of Mathematical Sciences, Nanyang Technological University, Singapore
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia

Abstract: Let $\mathcal H$ be a hypergraph with maximal vertex degree $\Delta$, such that each hyperedge of it has at least $\delta$ vertices. Let $k=\lceil\frac{2\Delta}\delta\rceil$. We prove that $\mathcal H$ admits a proper vertex coloring with $k+1$ colors, (i.e., in any hyperedge there should be at least two vertices of different colors). For $k\ge3$ and $\delta\ge3$ we prove that $\mathcal H$ admits a proper vertex coloring with $k$ colors.
For a graph $G$ set $k=\lceil\frac{2\Delta(G)}{\delta(G)}\rceil$. As a corollary we derive that there exists a proper dynamic coloring of the graph $G$ with $k+1$ colors, and for $k\ge3$ and $\delta(G)\ge3$ – with $k$ colors.

Key words and phrases: hypergraph, proper coloring, dynamic coloring.

UDC: 519.174.7+519.179.1

Received: 18.10.2011


 English version:
Journal of Mathematical Sciences (New York), 2012, 184:5, 595–600

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024