×

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.

MSC:
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI