Equitable colorings of nonuniform hypergraphs

被引:2
作者
Shirgazina, I. R. [1 ]
机构
[1] Moscow MV Lomonosov State Univ, Moscow, Russia
基金
俄罗斯基础研究基金会;
关键词
hypergraph; equitable coloring; simple hypergraph;
D O I
10.1134/S0001434616030147
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The well-known extremal problem on hypergraph colorings is studied. We investigate whether it is possible to color a hypergraph with a fixed number of colors equitably, i.e., so that, on the one hand, no edge is monochromatic and, on the other hand, the cardinalities of the color classes are almost the same. It is proved that if H = (V,E) is a simple hypergraph in which the least cardinality of an edge equals k, |V| = n, r|n, and 0 is an absolute constant, then there exists an equitable r-coloring of H.
引用
收藏
页码:444 / 456
页数:13
相关论文
共 12 条
  • [1] [Anonymous], PROBLEM ERDOS LOVASZ
  • [2] [Anonymous], 1963, NORDISK MAT TIDSKRIF
  • [3] 3-CHROMATIC HYPERGRAPHS
    BECK, J
    [J]. DISCRETE MATHEMATICS, 1978, 24 (02) : 127 - 137
  • [4] Erdos P., 1964, ACTA MATH ACAD SCI H, V15, P445, DOI DOI 10.1007/BF01897152
  • [5] Erdos P., 1961, ACTA MATH ACAD SCI H, V12, P87, DOI 10.1007/BF02066676
  • [6] Hajnal A., 1970, Colloq. Math. Soc. Janos Bolyai, V2, P601
  • [7] Kostochka A, 2006, BOLYAI MATH STUD, P175
  • [8] Lu LY, 2007, ELECTRON J COMB, V14
  • [9] The Erdos-Hajnal problem of hypergraph colouring, its generalizations, and related problems
    Raigorodskii, A. M.
    Shabanov, D. A.
    [J]. RUSSIAN MATHEMATICAL SURVEYS, 2011, 66 (05) : 933 - 1002
  • [10] Around Erdos-Lovasz problem on colorings of non-uniform hypergraphs
    Shabanov, Dmitry A.
    [J]. DISCRETE MATHEMATICS, 2015, 338 (11) : 1976 - 1981