Abstract:
Extremal problems concerned with hypergraph colouring first arose in connection with classical investigations in the 1920-30s which gave rise to Ramsey theory. Since then, this area has assumed a central position in extremal combinatorics. This survey is devoted to one well-known problem of hypergraph colouring, the Erdős–Hajnal problem, initially posed in 1961. It opened a line of research in hypergraph theory whose methods and results are widely used in various domains of discrete mathematics.
Bibliography: 109 titles.
Keywords:
hypergraph, hypergraph colourings, chromatic numbers, extremal set theory.
Citation:
A. M. Raigorodskii, D. A. Shabanov, “The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems”, Russian Math. Surveys, 66:5 (2011), 933–1002
\Bibitem{RaiSha11}
\by A.~M.~Raigorodskii, D.~A.~Shabanov
\paper The Erd\H os--Hajnal problem of hypergraph colouring, its generalizations, and related problems
\jour Russian Math. Surveys
\yr 2011
\vol 66
\issue 5
\pages 933--1002
\mathnet{http://mi.mathnet.ru/eng/rm9443}
\crossref{https://doi.org/10.1070/RM2011v066n05ABEH004764}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2919273}
\zmath{https://zbmath.org/?q=an:1251.05063}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2011RuMaS..66..933R}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000298661300003}
\elib{https://elibrary.ru/item.asp?id=20423298}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84855925923}
Linking options:
https://www.mathnet.ru/eng/rm9443
https://doi.org/10.1070/RM2011v066n05ABEH004764
https://www.mathnet.ru/eng/rm/v66/i5/p109
This publication is cited in the following 39 articles:
Axenovich M., Karrer A., “High Girth Hypergraphs With Unavoidable Monochromatic Or Rainbow Edges”, Discuss. Math. Graph Theory, 42:2 (2022), 471–484
D. D. Cherkashin, “On the Erdös–Hajnal Problem for 3-Graphs”, J Math Sci, 255:1 (2021), 103
A. M. Raigorodskii, D. D. Cherkashin, “Extremal problems in hypergraph colourings”, Russian Math. Surveys, 75:1 (2020), 89–146
D. A. Shabanov, T. M. Shaikheeva, “The List-Chromatic Number of Complete Multipartite Hypergraphs and Multiple Covers by Independent Sets”, Math. Notes, 107:3 (2020), 499–508
Yu. A. Demidovich, “2-Colorings of Hypergraphs with Large Girth”, Math. Notes, 108:2 (2020), 188–200
Yu. A. Demidovich, “New lower bound for the minimal number of edges of simple uniform hypergraph without the property Bk”, Discrete Math. Appl., 32:3 (2022), 155–176
Cherkashin D., Petrov F., “Regular Behavior of the Maximal Hypergraph Chromatic Number”, SIAM Discret. Math., 34:2 (2020), 1326–1333
Margarita Akhmejanova, Dmitry Shabanov, “Coloring hypergraphs with bounded cardinalities of edge intersections”, Discrete Mathematics, 343:4 (2020), 111692
M. Akhmejanova, D. A. Shabanov, “Equitable colorings of hypergraphs with r colors”, J. Math. Sci., 262:4 (2022), 391–405
Yu. A. Demidovich, “On some generalizations of the property B problem of an n-uniform hypergraph”, J. Math. Sci., 262:4 (2022), 457–475
A. E. Khuzieva, “Random constructions of hypergraphs with large girth and without panchromatic colorings”, J. Math. Sci., 262:4 (2022), 581–590
M. Akhmejanova, “On Equitable Colorings of Hypergraphs”, Math. Notes, 106:3 (2019), 319–326
D. D. Cherkashin, “On the Erdős–Hajnal problem in the case of 3-graphs”, Kombinatorika i teoriya grafov. XI, Zap. nauchn. sem. POMI, 488, POMI, SPb., 2019, 168–176
Wang L., Egorova E.K., Mokryakov A.V., “Development of Hypergraph Theory”, J. Comput. Syst. Sci. Int., 57:1 (2018), 109–114
I. A. Akolzin, “On 3-Homogeneous Hypergraphs Colorings in 3 Colors”, J. Math. Sci. (N. Y.), 250:6 (2020), 881–894
Citation in format AMSBIB
Contact us: