What type of study is this?

This is a Experimental Study study.

September 24, 2025Open Access

On extremal numbers of the triangle plus the four-cycle

Key Points

The new construction significantly enhances the lower bound of ${ ext{ex}}(n,\\{C_3,C_4\\})$ for dense graphs.
A key finding resolves a long-standing problem dating back to 1976 in extremal graph theory.
Graphs developed contain no triangles or four-cycles, achieving girth of at least five in arbitrary vertex counts.
This study's results directly challenge previous assumptions stated in Chung-Graham.

Abstract

Abstract For a family F of graphs, let {ex} (n, F) denote the maximum number of edges in an n -vertex graph which contains none of the members of F as a subgraph. A longstanding problem in extremal graph theory asks to determine the function {ex} (n, \C₃, C₄\). Here we give a new construction for dense graphs of girth at least five with arbitrary number of vertices, providing the first improvement on the lower bound of {ex} (n, \C₃, C₄\) since 1976. As a corollary, this yields a negative answer to a problem in Chung-Graham 3.

On extremal numbers of the triangle plus the four-cycle

Key Points

Abstract

Cite This Study

Also Consider

Also Consider