Ahanjideh–Ekim–Yıldız conjecture for Z(d)Z(d)

About 4 years old · traced to

For odd dd, let Z(d)Z(d) denote the maximum matching number of a factor-critical, almost regular, triangle-free graph of maximum degree dd in the class used by the paper. The paper establishes the value of Z(d)Z(d) for even dd and for d∈{3,5}d\in\{3,5\}, and gives bounds for the remaining odd values.

Z(d)Z(d) conjecture. For odd d≥21d\geq 21,

Z(d)=⌊5(d+1)4⌋.Z(d)=\left\lfloor\frac{5(d+1)}{4}\right\rfloor.

Determining Z(d)Z(d) is crucial for evaluating the proposed extremal formula and constructing the corresponding graphs. The conjecture is motivated by results suggesting that sufficiently dense triangle-free graphs are blow-ups of a 55-cycle, but the stated range remains open in the paper.

References

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).

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.