A Bound on the Number of Edges in Graphs Without an Even Cycle

DOI10.1017/S0963548316000134MaRDI QIDQ5366930zbMATH OpenOpenAlexFDO

Authors Boris Bukh, Zilin Jiang

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

extremal graphs

Mathematics Subject Classification ID

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

Abstract: We show that, for each fixed $k$, an $n$-vertex graph not containing a cycle of length $2k$ has at most $80sqrtklogkcdot{n}^{1+1/k}+O(n)$ edges.

Recommendations

• A lower bound for the number of edges in a graph containing no two cycles of the same length
• On the maximum number of odd cycles in graphs without smaller odd cycles
• Edge maximal non-bipartite graphs without odd cycles of prescribed lengths
• scientific article; zbMATH DE number 1824729
• scientific article; zbMATH DE number 7144824
• Bounding the number of cycles in a graph in terms of its degree sequence
• Erratum For ‘A Bound on the Number of Edges in Graphs Without an Even Cycle’
• A note on graphs without short even cycles
• scientific article; zbMATH DE number 3931048
• scientific article; zbMATH DE number 1548426

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• A note on the Turán function of even cycles
• Constructions of bipartite graphs from finite geometries
• Cycles of even length in graphs
• Explicit construction of graphs with an arbitrary large girth and of large size
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Minimal Regular Graphs of Girths Eight and Twelve
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• On arithmetic progressions of cycle lengths in graphs
• On the Turán number for the hexagon
• The history of degenerate (bipartite) extremal graph problems
• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
• What we know and what we do not know about Turán numbers

Cited in

(30)

• scientific article; zbMATH DE number 7144824 (Why is no real title available?)
• A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Degree Ramsey numbers for even cycles
• Graphs without theta subgraphs
• The Ramsey number of a long even cycle versus a star
• A note on graphs without short even cycles
• Minimum number of edges that occur in odd cycles
• On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles
• A new upper bound on extremal number of even cycles
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• Erratum For ‘A Bound on the Number of Edges in Graphs Without an Even Cycle’
• Spectral extremal problem on \(t\) copies of \(\ell\)-cycles
• Extremal numbers of hypergraph suspensions of even cycles
• Hypergraphs with Few Berge Paths of Fixed Length between Vertices
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
• Linear cycles of consecutive lengths
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• The Turán number of directed paths and oriented cycles
• Orthonormal representations of \(H\)-free graphs
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
• Forbidding induced even cycles in a graph: typical structure and counting
• On some cycles in Wenger graphs
• On 3-uniform hypergraphs without a cycle of a given length
• Cycles in graphs of fixed girth with large size
• Anti-Ramsey numbers of paths and cycles in hypergraphs
• Cycles of given lengths in hypergraphs
• Making an H $H$‐free graph k $k$‐colorable

This page was built for publication: A Bound on the Number of Edges in Graphs Without an Even Cycle

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