Subgraph densities in \(K_r\)-free graphs
type: Item
instance of: scholarly article
title: Subgraph densities in \(K_r\)-free graphs
DOI: 10.37236/11329
author: A. Grzesik
author: Nika Salia
author: Casey Tompkins
author: Ervin Győri
published in: The Electronic Journal of Combinatorics
publication date: 2023-04-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/2205.13455
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C42
zbMATH DE Number: 7676069
zbMATH Keywords: pentagon density
zbMATH Keywords: triangle-free graphs
zbMATH Keywords: extremal graph theory
MaRDI profile type: Publication
OpenAlex ID: W4360849062
cites work: Many \(T\) copies in \(H\)-free graphs
cites work: Q5724802
cites work: On Turán-good graphs
cites work: Counting copies of a fixed subgraph in \(F\)-free graphs
cites work: On the maximum number of five-cycles in a triangle-free graph
cites work: On the maximal number of certain subgraphs in \(K_ r\)-free graphs
cites work: Q5812325
cites work: On the number of pentagons in triangle-free graphs
cites work: Maximizing five-cycles in \(K_r\)-free graphs
description: scientific article; zbMATH DE number 7676069