Excluding induced subgraphs. II: Extremal graphs (Q686271)

This paper, the second one in a sequence of papers of the authors [for Part I see Random Struct. Algorithms 2, 55-71 (1991; Zbl 0763.05046); for Part III see Random Struct. Algorithms 3, 19-31 (1992; Zbl 0751.05041)], studies properties of classes of finite graphs not containing a fixed subgraph \(H\) as an induced subgraph. For this the authors introduce a new parameter \(\tau(H)\) which is a direct generalization of the chromatic number \(\chi(H)\) and the clique covering number \(\sigma(H)\). Then they show that fundamental results of extremal graph theory for weak subgraphs, as for example the Erdős-Stone-Simonovits Theorems [\textit{P. Erdős} and \textit{M. Simonovits}, A limit theorem in graph theory, Stud. Sci. Math. Hungar. 1, 51-57 (1966; Zbl 0178.273); \textit{P. Erdős} and \textit{A. H. Stone}, On the structure of linear graphs, Bull. Am. Math. Soc. 52, 1087-1091 (1946)] and some structural results, carry over to induced subgraphs, if one replaces the chromatic number \(\chi(H)\) by the parameter \(\tau(H)\) in the statement of the corresponding theorem.