Erdős–Tuza conjecture on K4K_4-saturating edges

Let GG be an nn-vertex K4K_4-free graph. An edge in G\overline{G} is K4K_4-saturating if adding it to GG creates a copy of K4K_4. Let f(n,e)f(n,e) be the maximum integer \ell such that every nn-vertex K4K_4-free graph with ee edges has at least \ell K4K_4-saturating edges.

Erdős–Tuza conjecture.

f(n,n2/4+1)=(1+o(1))n216.f(n,\lfloor n^2/4\rfloor+1)=(1+o(1))\frac{n^2}{16}.

Equivalently, every nn-vertex K4K_4-free graph with n2/4+1\lfloor n^2/4\rfloor+1 edges has at least (1+o(1))n2/16(1+o(1))n^2/16 K4K_4-saturating edges. This is an Erdős–Rademacher-type extremal problem: adding one edge beyond the Turán bound for K4K_4-free graphs should force quadratically many saturating non-edges. The supplied text gives no resolution, so the conjecture is recorded as open.

Sources & referencesView supporting material

Primary source

József Balogh and Hong Liu, “On the number of K_4-saturating edges”, arXiv:1312.5248 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.