TY - JOUR

T1 - On proper colorings of hypergraphs

AU - Gravin, N. V.

AU - Karpov, D. V.

PY - 2012/8/1

Y1 - 2012/8/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84884341123&partnerID=8YFLogxK

U2 - 10.1007/s10958-012-0884-2

DO - 10.1007/s10958-012-0884-2

M3 - Article

AN - SCOPUS:84884341123

VL - 184

SP - 595

EP - 600

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 5

ER -