zbMATH — the first resource for mathematics

The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems. (English. Russian original) Zbl 1251.05063
Russ. Math. Surv. 66, No. 5, 933-1002 (2011); translation from Usp. Mat. Nauk. 66, No. 3, 109-182 (2011).
In 1961 P. Erdős and A. Hajnal [Acta Math. Acad. Sci. Hung. 12, 87–123 (1961; Zbl 0201.32801)] posed the following problem: Find the minimum possible number \(m(n)\) of edges of a hypergraph in the class of \(n\)-uniform hypergraphs with chromatic number greater than 2. The natural generalisation of the problem for higher chromatic number was formulated by M. Herzog and J. Schönheim [J. Comb. Theory, Ser. B 12, 41-49 (1972; Zbl 0236.05123)]. The paper provides a summary of the present state of the research related to these problems and their variations.

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C65 Hypergraphs
Full Text: DOI