Extremal graphs without 4-cycles

DOI10.1016/J.JCTB.2013.01.001zbMATH Open1301.05186arXiv1201.4912OpenAlexW2005344823MaRDI QIDQ744158FDOQ744158

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Über ein Problem von K. Zarankiewicz
• Graphs without quadrilaterals
• Title not available (Why is that?)
• On the number of edges of quadrilateral-free graphs
• Polarities in finite projective planes
• Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
• Graphs without four-cycles
• Title not available (Why is that?)

Cited In (18)

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

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)