Research output: Contribution to journal › Article › peer-review
On proper colorings of hypergraphs. / Gravin, N. V.; Karpov, D. V.
In: Journal of Mathematical Sciences (United States), Vol. 184, No. 5, 01.08.2012, p. 595-600.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 36925494