On the maximum number of odd cycles in graphs without smaller odd cycles

DOI10.1002/JGT.22738zbMATH Open1522.05208arXiv1806.09953OpenAlexW2981387241WikidataQ114236148 ScholiaQ114236148MaRDI QIDQ6056808FDOQ6056808

Bartłomiej Kielak, A. Grzesik

Publication date: 4 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We prove that for each odd integer $kgeq7$, every graph on $n$ vertices without odd cycles of length less than $k$ contains at most $(n/k{)}^k$ cycles of length $k$. This generalizes the previous results on the maximum number of pentagons in triangle-free graphs, conjectured by ErdH{o}s in 1984, and asymptotically determines the generalized Tur'an number $mathrmex(n,C_k,C_{k-2})$ for odd $k$. In contrary to the previous results on the pentagon case, our proof is not computer-assisted.

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

Recommendations

• scientific article; zbMATH DE number 3931048
• Extremal numbers for odd cycles
• Edge maximal non-bipartite graphs without odd cycles of prescribed lengths
• Graphs with large maximum degree containing no odd cycles of a given length
• Even cycles in graphs with many odd cycles

zbMATH Keywords

extremal problemscyclescycle-free

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cites Work

• On the number of pentagons in triangle-free graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• On the structure of linear graphs
• On the maximum number of five-cycles in a triangle-free graph
• What we know and what we do not know about Turán numbers
• Title not available (Why is that?)
• On the inducibility of cycles
• Pentagons vs. triangles
• The inducibility of graphs
• On the number of \(C_ 5's\) in a triangle-free graph
• The maximum number of triangles in \(C_{2k+1}\)-free graphs
• Title not available (Why is that?)
• On 3-uniform hypergraphs without a cycle of a given length
• Many \(T\) copies in \(H\)-free graphs
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• Pentagons in triangle-free graphs
• Extremal problems for cycles in graphs
• A bound on the inducibility of cycles
• Generalized Turán problems for even cycles
• A Generalized Turán Problem and its Applications
• Title not available (Why is that?)

Cited In (15)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the generalized Turán problem for odd cycles
• Minimum number of edges that occur in odd cycles
• Graphs without short odd cycles are nearly bipartite
• Multicolor Turán numbers. II: A generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles
• Graphs with large maximum degree containing no odd cycles of a given length
• The maximum number of paths of length three in a planar graph
• Edge maximal non-bipartite graphs without odd cycles of prescribed lengths
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• Extremal problems involving vertices and edges on odd cycles
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: On the maximum number of odd cycles in graphs without smaller odd cycles

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