Research output: Contribution to journal › Article › peer-review
Let ℋ be a hypergraph with maximal vertex degree Δ such that each its hyperedge has at least δ vertices. Let k = [2Δ/δ]. We prove that ℋ admits a proper vertex coloring with k + 1 colors (i.e., such that any hyperedge contains at least two vertices of different colors). For k ≥ 3 and δ ≥ 3 we prove that ℋ admits a proper vertex coloring with k colors.For a graph G set k = [2Δ (G)/δ (G)]. As a corollary, we prove that there exists a dynamic coloring of the graph G with k + 1 colors in general and with k colors if δ(G) ≥ 3 and k ≥ 3. Bibliography: 16 titles.
Original language | English |
---|---|
Pages (from-to) | 595-600 |
Number of pages | 6 |
Journal | Journal of Mathematical Sciences (United States) |
Volume | 184 |
Issue number | 5 |
DOIs | |
State | Published - 1 Aug 2012 |
ID: 36925494