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

From papers

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 d21d\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.

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.