The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems. (English. Russian original) Zbl 1251.05063

Raigorodskii, A. M.; Shabanov, D. A.

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.

Reviewer: Gabriel Semanišin (Košice)

MSC:

05C15	Coloring of graphs and hypergraphs
05C35	Extremal problems in graph theory
05C65	Hypergraphs

Keywords:

hypergraph; hypergraph colouring; chromatic number; extremal set theory