Extremal K₄-minor-free graphs without short cycles

2021/11/10 by János Barát, Barát, János
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2111.05712

Abstract

We determine the maximum number of edges in a K₄-minor-free n-vertex graph of girth g, when g = 5 or g is even. We argue that there are many different n-vertex extremal graphs, if n is even and g is odd.

Related

• On extremal numbers of the triangle plus the four-cycle
• A simple proof for the lower bound of the girth of graphs D(n, q)
• Extremal C4-free/C5-free planar graphs
• Extremal results regarding K₆-minors in graphs of girth at least 5
• Improved lower bounds on the maximum size of graphs with girth 5