Ahanjideh–Ekim–Yıldız formula for maximum edges in triangle-free graphs

From papers

For a positive integer dd, let Z(d)Z(d) denote the relevant extremal matching-number threshold, and let fΔ(d,m)f_{\Delta}(d,m) be the maximum number of edges in a triangle-free graph with matching number mm and maximum degree bounded in the setting of the source. For natural numbers d2d\geq 2 and mm, write

m=kZ(d)+r.m=kZ(d)+r.

Ahanjideh–Ekim–Yıldız conjecture. For all natural numbers d2d\geq 2 and mm, we have

fΔ(d,m)={dm+kd/2,if r<d,dm+kd/2+rd+1,if rd.f_{\Delta}(d,m)=\begin{cases} dm+k\left\lfloor d/2\right\rfloor,&\text{if }r<d,\\ dm+k\left\lfloor d/2\right\rfloor+r-d+1,&\text{if }r\geq d.\end{cases}

This formula extends the cases established in the source to the remaining open cases and would give the general edge-extremal function for the considered class of triangle-free graphs.

Progress summary

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

Sources & referencesView supporting material

Primary source

Ali Erdem Banak, Tınaz Ekim and Z. Caner Taşkın, “Constructing extremal triangle-free graphs using integer programming”, arXiv:2304.01729 (2023).

Solutions 0

No solutions have been posted yet.