Subgraph densities in \(K_r\)-free graphs
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.
scientific article; zbMATH DE number 7676069
scientific article