# Extremal C t-free graphs

From Combinatorics Wiki

This topic is currently being edited. New and more complete information will be added soon. Thank-you for your patience.

## Introduction

A graph *G* is an extremal *C _{t}*-free graph if

*G*has maximal size and girth

*g*at least

*t+1*. The set of extremal

*C*-free graphs is denoted by

_{t}*EX(n;t)=EX(n;{C*and the size of the graph is the extremal number

_{3},C_{4},...,C_{t}})*ex(n;t)=ex(n;{C*.

_{3},C_{4},...,C_{t}})## Known Results

This section includes links to tables that present a summary of current known values of *ex(n;t)* for ex(n;4), ex(n;5), ex(n;6), ex(n;7) and ex(n;8). Additionally, the table ex(n;t) lists some known values for *ex(n;t)* for *n=1,2,...,50* and *t=4,5,...,13*.

If the exact value of *ex(n;t)* is known then the value is shown in bold text, where the exact value of *ex(n;t)* is not yet known constructive lower bounds are displayed in the table cells. When there are two values in the table cell these represent the current known upper and lower bounds of the extremal number. The background colour of the table cells indicates the source of these values. The key to the colours is in another table below the known values.

For for *n* ≤ *t*, it is easy to show that the Stars *K _{1,n-1}* and Paths

*P*are extremal graphs and

_{n}*ex(n;t)=n-1*. For

*t+1*≤

*n*≤ [math]\lfloor 3t/2 \rfloor [/math] the Cycles

*C*are extremal graphs and

_{n}*ex(n;t)=n*. These values are included in the tables as folklore.

The problem of finding the extremal number *ex(n;3)* is solved by Mantel's theorem which states that the maximum size of a triangle free graph of order *n* is [math]\lfloor {{n^2}/4}\rfloor[/math]. The extremal graphs [math]EX(n;3)[/math] are the complete bipartite graphs [math]K_{{\lfloor n/2 \rfloor}{\lceil n/2 \rceil}}[/math].

## References

<references />