Acyclic matching lower bound for graphs of bounded maximum degree

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.

Sources & referencesView supporting material

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.