Ahanjideh–Ekim–Yıldız general formula for triangle-free extremal graphs in terms of Z(d)Z(d)

From papers

Let dd and mm be natural numbers, let Z(d)Z(d) be the parameter defined by the largest matching number of the relevant factor-critical triangle-free graph, and write

m=kZ(d)+r,0r<Z(d).m=kZ(d)+r,\qquad 0\leq r<Z(d).

Let f(d,m)f_{\vartriangle}(d,m) denote the maximum number of edges in a triangle-free graph with maximum degree at most dd and matching number at most mm.

General formula in terms of Z(d)Z(d).

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

The formula is presented as a consequence of the intermediate-value conjecture and would extend the theorem to all integers dd and mm. Thus it remains conjectural whenever that preceding conjecture is unresolved.

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

Milad Ahanjideh, Tınaz Ekim and Mehmet Akif Yıldız, “Maximum size of a triangle-free graph with bounded maximum degree and matching number”, arXiv:2207.02271 (2022).

Solutions 0

No solutions have been posted yet.