Acyclic matching lower bound for graphs of bounded maximum degree

About 9 years old · traced to

Let GG be a graph with no isolated vertices, let Δ\Delta be its maximum degree, let n(G)n(G) denote its number of vertices, and let νac(G)\nu_{ac}(G) denote its acyclic matching number. The maximum-degree acyclic matching conjecture.

νac(G)≥min⁡{2n(G)(⌈Δ2⌉+1)(⌊Δ2⌋+1),n(G)2Δ}.\nu_{ac}(G) \geq \min\left\{\frac{2n(G)}{\left(\left\lceil\frac{\Delta}{2}\right\rceil+1\right)\left(\left\lfloor\frac{\Delta}{2}\right\rfloor+1\right)},\frac{n(G)}{2\Delta}\right\}.

This would extend the paper's acyclic matching lower bounds from subcubic graphs to arbitrary maximum degree. The source gives no resolution status, so the conjecture remains open.

References

Primary source

M. Fürst and D. Rautenbach, “A lower bound on the acyclic matching number of subcubic graphs”, arXiv:1710.10076 (2017).

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.