×

The history of degenerate (bipartite) extremal graph problems. (English) Zbl 1296.05098

Lovász, László (ed.) et al., Erdős centennial. On the occasion of Paul Erdős 100th anniversary of his birth. Berlin: Springer; Budapest: János Bolyai Mathematical Society (ISBN 978-3-642-39285-6/hbk; 978-3-642-39286-3/ebook). Bolyai Society Mathematical Studies 25, 169-264 (2013).
This is an extensive survey of the work that has been done and is in progress on the degenerate (bipartite) extremal graph theory problem. The bibliography contains 257 references. Since the two authors have been very active in the development of this line of research and are aware of the current activity, there are a considerable number of references to papers that are now in progress, which makes the survey even more valuable. The survey does more than merely review the important results that have been proved, but also is careful to describe the methods, uses, and constructions central to the development of the field, and also to describe open problems that are central to the continued development. To give some feel of the general topics covered, the following is a list of the titles of the sections of the survey: 1) Introduction, 2) The general theory, classification, 3) Excluding complete bipartite graphs, 4) Excluding cycles \(C_2k\), 5) Paths and long cycles, 6) Excluding trees, 7) More complex excluded subgraphs, 8) Eigenvalues and extremal problems, 9) Excluding topological subdivisions, 10) Hypergraph extremal problems, 11) Supersaturated graphs, 12) Ordered structures, 13) Applications in geometry, 14) Further connections and problems.
For the entire collection see [Zbl 1272.00039].

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics