Subgraph densities in \(K_r\)-free graphs (Q2699640)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Subgraph densities in \(K_r\)-free graphs |
scientific article |
Statements
Subgraph densities in \(K_r\)-free graphs (English)
0 references
19 April 2023
0 references
Summary: A counterexample to a recent conjecture of \textit{B. Lidický} and \textit{K. Murphy} [Eur. J. Comb. 97, Article ID 103367, 29 p. (2021; Zbl 1469.05088)] on the structure of \(K_r\)-free graph maximizing the number of copies of a given graph with chromatic number at most \(r-1\) is known in the case \(r=3\). Here, we show that this conjecture does not hold for any \(r\), and that the structure of extremal graphs can be richer. We also provide an alternative conjecture and, as a step towards its proof, we prove an asymptotically tight bound on the number of copies of any bipartite graph of radius at most 2 in the class of triangle-free graph.
0 references
pentagon density
0 references
triangle-free graphs
0 references
extremal graph theory
0 references