This article is cited in 41 papers

The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems

A. M. Raigorodskii^ab, D. A. Shabanov<sup>ab

a</sup> M. V. Lomonosov Moscow State University
^b Moscow Institute of Physics and Technology

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.

UDC: 519.112.7+519.174+519.179.1

MSC: 05C15, 05C35, 05C65

Received: 01.11.2010

DOI: 10.4213/rm9443

 English version: Russian Mathematical Surveys, 2011, 66:5, 933–1002

Bibliographic databases:

• 
• 
• 
• 
• 
• 
•