Subgraph densities in K_r-free graphs

DOI10.37236/11329MaRDI QIDQ2699640zbMATH OpenOpenAlexFDO

Authors A. Grzesik, Nika Salia, Casey Tompkins, Ervin Győri

Publication date 19 April 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2205.13455

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal graph theorypentagon densitytriangle-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

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.

Recommendations

• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• The number of \(K_{s,t}\)-free graphs
• H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• Many \(T\) copies in \(H\)-free graphs

Cites work

• Counting copies of a fixed subgraph in F-free graphs
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• Many \(T\) copies in \(H\)-free graphs
• Maximizing five-cycles in \(K_r\)-free graphs
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• On the maximum number of five-cycles in a triangle-free graph
• On the number of pentagons in triangle-free graphs
• On Turán-good graphs

Cited in

(11)

• Dense subgraphs in the H-free process
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• On a conjecture of Nagy on extremal densities
• Subgraph densities in a surface
• Counterexamples to Gerbner's conjecture on stability of maximal F‐free graphs
• Every graph is eventually Turán-good
• Subgraph densities in K_r-free graphs
• On triangle-free graphs maximizing embeddings of bipartite graphs
• Generalized regular Turán numbers
• On weakly Turán-good graphs

This page was built for publication: Subgraph densities in \(K_r\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2699640)