Erdős–Tuza conjecture on K4K_4-saturating edges

About 13 years old · traced to

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.

References

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.