# The Library

### Supersaturation problem for color-critical graphs

Tools

Pikhurko, Oleg and Yilma, Z. B.
*Supersaturation problem for color-critical graphs.*

**Research output not available from this repository, contact author.**

## Abstract

The \emph{Tur\'an function} $\ex(n,F)$ of a graph $F$ is the maximum number of edges in an $F$-free graph with $n$ vertices. The classical results of Tur\'an and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine $h_F(n,q)$, the minimum number of copies of $F$ that a graph with $n$ vertices and $\ex(n,F)+q$ edges can have.

We determine $h_F(n,q)$ asymptotically when $F$ is \emph{color-critical} (that is, $F$ contains an edge whose deletion reduces its chromatic number) and $q=o(n^2)$.

Determining the exact value of $h_F(n,q)$ seems rather difficult. For example, let $c_1$ be the limit superior of $q/n$ for which the extremal structures are obtained by adding some $q$ edges to a maximal $F$-free graph. The problem of determining $c_1$ for cliques was a well-known question of Erd\H os that was solved only decades later by Lov\'asz and Simonovits. Here we prove that $c_1>0$ for every {color-critical} $F$. Our approach also allows us to determine $c_1$ for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.

Item Type: | Submitted Journal Article |
---|---|

Divisions: | Faculty of Science > Mathematics |

Status: | Peer Reviewed |

Request changes or add full text files to a record

### Repository staff actions (login required)

View Item |