Excluding induced subgraphs. II: Extremal graphs
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.
- Excluding Induced Subgraphs III: A General Asymptotic
- Excluding induced subgraphs: quadrilaterals
- Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
- scientific article; zbMATH DE number 3841900 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3258858 (Why is no real title available?)
- scientific article; zbMATH DE number 3262986 (Why is no real title available?)
- scientific article; zbMATH DE number 3285073 (Why is no real title available?)
- On the chromatic number of random graphs
- On the Erdös-Stone Theorem
- On the structure of linear graphs
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- The chromatic number of random graphs
- Über ein Problem von K. Zarankiewicz
- Structure and enumeration theorems for hereditary properties in finite relational languages
- Induced saturation of graphs
- Forbidding induced even cycles in a graph: typical structure and counting
- The number of graphs without forbidden subgraphs
- The speed of hereditary properties of graphs
- Hereditary classes of graphs: a parametric approach
- Counting \(r\)-graphs without forbidden configurations
- Almost all string graphs are intersection graphs of plane convex sets
- On induced saturation for paths
- \((k,l)\)-colourings and Ferrers diagram representations of cographs
- On the abstract chromatic number and its computability for finitely axiomatizable theories
- Classes of graphs without star forests and related graphs
- Graphs with large obstacle numbers
- A note on the bichromatic numbers of graphs
- A Brooks-type theorem for the bichromatic number
- Stability-type results for hereditary properties
- The edit distance function and symmetrization
- Excluding Induced Subgraphs III: A General Asymptotic
- scientific article; zbMATH DE number 47438 (Why is no real title available?)
- Excluding Subdivisions of Infinite Cliques
- Locally bounded coverings and factorial properties of graphs
- scientific article; zbMATH DE number 475587 (Why is no real title available?)
- Induced Turán numbers
- Boundary properties of factorial classes of graphs
- Almost all string graphs are intersection graphs of plane convex sets
- Excluding a substar and an antisubstar
- Deciding the Bell number for hereditary graph properties
- The structure and the number of \(P_7\)-free bipartite graphs
- The structure and the number of \(P_7\)-free bipartite graphs
- Measures on monotone properties of graphs
- Induced Turán problems and traces of hypergraphs
- The regularity of almost all edge ideals
- The structure of almost all graphs in a hereditary property
- For most graphs H, most H-free graphs have a linear homogeneous set
- On the structure of graphs with low obstacle number
- Typical structure of hereditary graph families. II: Exotic examples
- The maximum edit distance from hereditary graph properties
This page was built for publication: Excluding induced subgraphs. II: Extremal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686271)
