Erdős–Tuza conjecture on -saturating edges
Erdős–Tuza conjecture on -saturating edges
Let be an -vertex -free graph. An edge in is -saturating if adding it to creates a copy of . Let be the maximum integer such that every -vertex -free graph with edges has at least -saturating edges.
Erdős–Tuza conjecture.
Equivalently, every -vertex -free graph with edges has at least -saturating edges. This is an Erdős–Rademacher-type extremal problem: adding one edge beyond the Turán bound for -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.