Geodesic
Equitable Colorings of Nonuniform Hypergraphs
Matematičeskie zametki, Tome 99 (2016) no. 3, pp. 441-456.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $$ \sum_{e \in E}r^{1-|e|}\le c \sqrt{k}\,, $$ where $c>0$ is an absolute constant, then there exists an equitable $r$-coloring of $H$.
Keywords: hypergraph, equitable coloring, simple hypergraph. 
@article{MZM_2016_99_3_a13,
     author = {I. R. Shirgazina},
     title = {Equitable {Colorings} of {Nonuniform} {Hypergraphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {441--456},
     publisher = {mathdoc},
     volume = {99},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a13/}
}
TY  - JOUR
AU  - I. R. Shirgazina
TI  - Equitable Colorings of Nonuniform Hypergraphs
JO  - Matematičeskie zametki
PY  - 2016
SP  - 441
EP  - 456
VL  - 99
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a13/
LA  - ru
ID  - MZM_2016_99_3_a13
ER  - 
%0 Journal Article
%A I. R. Shirgazina
%T Equitable Colorings of Nonuniform Hypergraphs
%J Matematičeskie zametki
%D 2016
%P 441-456
%V 99
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a13/
%G ru
%F MZM_2016_99_3_a13
I. R. Shirgazina. Equitable Colorings of Nonuniform Hypergraphs. Matematičeskie zametki, Tome 99 (2016) no. 3, pp. 441-456. http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a13/

[1] P. Erdős, A. Hajnal, “On a property of families of sets”, Acta Math. Acad. Sci. Hungar, 12 (1961), 87–123 | MR | Zbl

[2] P. Erdős, “On a combinatorial problem”, Nordisk Matematisk Tidsskrift, 11 (1963), 5–10 | MR | Zbl

[3] P. Erdős, “On a combinatorial problem. II”, Acta Math. Acad. Sci. Hungar, 15 (1964), 445–447 | MR | Zbl

[4] A. V. Kostochka, “Color-critical graphs and hypergraphs with few edges: a survey”, More Sets, Graphs and Numbers, Bolyai Soc. Math. Stud., 15, Springer-Verlag, Berlin, 2006, 175–198 | MR | Zbl

[5] A. M. Raigorodskii, D. A. Shabanov, “Zadacha Erdesha–Khainala o raskraskakh gipergrafov, ee obobscheniya i smezhnye problemy”, UMN, 66:5 (2011), 109–182 | DOI | MR | Zbl

[6] P. Erdős, L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. Janos Bolyai, 10, North Holland, Amsterdam, 1975, 609–627 | MR | Zbl

[7] J. Beck, “On 3-chromatic hypergraphs”, Discrete Math., 24:2 (1978), 127–137 | DOI | MR | Zbl

[8] L. Lu, On a problem of Erdős and Lovász on coloring non-uniform hypergraphs, www.math.sc.edu/~lu/papers/propertyB.pdf

[9] D. A. Shabanov, “Around Erdős–Lovász problem on colorings of non-uniform hypergraphs”, Discrete Math., 338:11 (2015), 1976–1981 | DOI | MR | Zbl

[10] D. A. Shabanov, “Coloring non-uniform hypergraphs without short cycles”, Graphs Combin., 30:5 (2014), 1249–1260 | DOI | MR | Zbl

[11] A. Hajnal, E. Szemerédi, “Proof of a conjecture of P. Erdős”, Combinatorial Theory and Its Applications, North-Holland, Amsterdam, 1970, 601–623 | MR | Zbl

[12] L. Lu, L. Székely, “Using Lovász Local Lemma in the space of random injections”, Electron. J. Combin., 14:1 (2007), Research Paper R63 | MR | Zbl

[13] D. A. Shabanov, “Equitable two-colorings of uniform hypergraphs”, European J. Combin., 43 (2015), 185–203 | DOI | MR | Zbl