Geodesic
On Equitable Colorings of Hypergraphs
Matematičeskie zametki, Tome 106 (2019) no. 3, pp. 323-332.

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

A two-coloring is said to be equitable if, on the one hand, there are no monochromatic edges (the coloring is regular) and, on the other hand, the cardinalities of color classes differ from one another by at most $1$. It is proved that, for the existence of an equitable two-coloring, it suffices that the number of edges satisfy an estimate of the same order as that for a regular coloring. This result strengthens the previously known Radhakrishnan–Srinivasan theorem.
Keywords: hypergraph, hypergraph coloring, equitable coloring, equitable two-coloring. 
@article{MZM_2019_106_3_a0,
     author = {M. Akhmejanova},
     title = {On {Equitable} {Colorings} of {Hypergraphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {323--332},
     publisher = {mathdoc},
     volume = {106},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2019_106_3_a0/}
}
TY  - JOUR
AU  - M. Akhmejanova
TI  - On Equitable Colorings of Hypergraphs
JO  - Matematičeskie zametki
PY  - 2019
SP  - 323
EP  - 332
VL  - 106
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2019_106_3_a0/
LA  - ru
ID  - MZM_2019_106_3_a0
ER  - 
%0 Journal Article
%A M. Akhmejanova
%T On Equitable Colorings of Hypergraphs
%J Matematičeskie zametki
%D 2019
%P 323-332
%V 106
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2019_106_3_a0/
%G ru
%F MZM_2019_106_3_a0
M. Akhmejanova. On Equitable Colorings of Hypergraphs. Matematičeskie zametki, Tome 106 (2019) no. 3, pp. 323-332. http://geodesic.mathdoc.fr/item/MZM_2019_106_3_a0/

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

[2] J. Radhakrishnan, A. Srinivasan, “Improved bounds and algorithms for hypergraph 2-coloring”, Random Structures Algorithms, 16:1 (2000), 4–32 | MR

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

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

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

[6] P. Erdős, “Extremal problems in graph theory”, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, 1964, 29–36 | MR

[7] H. A. Kierstead, A. V. Kostochka, “A short proof of the Hajnal–Szemerédi theorem on equitable colouring”, Combin. Probab. Comput., 17:2 (2008), 265–270 | DOI | MR

[8] H. A. Kierstead, A. V. Kostochka, M. Mydlarz, E. Szemerédi, “A fast algorithm for equitable coloring”, Combinatorica, 30:2 (2010), 217–224 | DOI | MR

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