|
Zapiski Nauchnykh Seminarov POMI, 2011, Volume 391, Pages 79–89
(Mi znsl4569)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Received: 18.10.2011
Citation:
N. V. Gravin, D. V. Karpov, “On proper colorings of hypergraphs”, Combinatorics and graph theory. Part III, Zap. Nauchn. Sem. POMI, 391, POMI, St. Petersburg, 2011, 79–89; J. Math. Sci. (N. Y.), 184:5 (2012), 595–600
Linking options:
https://www.mathnet.ru/eng/znsl4569 https://www.mathnet.ru/eng/znsl/v391/p79
|
Statistics & downloads: |
Abstract page: | 244 | Full-text PDF : | 86 | References: | 42 |
|