Extremal graphs without 4-cycles

DOI10.1016/J.JCTB.2013.01.001MaRDI QIDQ744158zbMATH OpenOpenAlexFDO

Authors Frank A. Firke, Peter M. Kosek, Evan D. Nash, Jason S. Williford

Publication date 6 October 2014

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

\(C_4\)-free graphupper bound for the number of edges

Mathematics Subject Classification ID

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

Abstract: We prove an upper bound for the number of edges a C4-free graph on q^2 + q vertices can contain for q even. This upper bound is achieved whenever there is an orthogonal polarity graph of a plane of even order q.

Recommendations

• Some extremal results on 4-cycles
• Upper bounds on the extremal number of the 4‐cycle
• Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
• On the number of edges of quadrilateral-free graphs
• Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

Cites work

• Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
• Graphs without four-cycles
• Graphs without quadrilaterals
• scientific article; zbMATH DE number 89768 (Why is no real title available?)
• scientific article; zbMATH DE number 1943958 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• On the number of edges of quadrilateral-free graphs
• Polarities in finite projective planes
• Über ein Problem von K. Zarankiewicz

Cited in

(20)

• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Some new upper bounds of \(\operatorname{ex}(n;\{C_3,C_4\})\)
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• Some extremal results on 4-cycles
• Extremal digraphs avoiding an orientation of \(C_4\)
• The Turán number of directed paths and oriented cycles
• Orthogonal polarity graphs and Sidon sets
• On graphs and algebraic graphs that do not contain cycles of length 4
• scientific article; zbMATH DE number 89768 (Why is no real title available?)
• Extremal graphs of order dimension 4
• scientific article; zbMATH DE number 2145243 (Why is no real title available?)
• Turán numbers of theta graphs
• ON A PROBLEM OF ERDŐS ABOUT GRAPHS WHOSE SIZE IS THE TURÁN NUMBER PLUS ONE
• Maximum cardinality neighbourly sets in quadrilateral free graphs
• On 4-connected graphs without even cycle decompositions
• Upper bounds on the extremal number of the 4‐cycle
• Upper bounds on the multicolor Ramsey numbers \(r_k (C_4)\)
• Some exact results on 4-cycles: stability and supersaturation
• Ramsey numbers of \(C_4\) versus wheels and stars
• Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size

This page was built for publication: Extremal graphs without 4-cycles

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