Summary: Let \(G\) be a graph with edge ideal \(I(G)\). We recall the notions, given by S. A. Seyed Fakhari and S. Yassemi [Collect. Math. 69, No. 2, 249–262 (2018; Zbl 1391.13024)], of min-match\(_{\{K_{2}, C_{5}\}} (G)\) and ind-match\(_{\{ K_{2}, C_{5}\}}(G)\). We show that \[\mathrm{reg}(I(G)^s)\leq 2s +\,\text{min-match}_{\{K_{2}, C_{5}\}}(G)-1,\] for all \(s \geq 1\), which implies that \[\mathrm{reg}(I(G)^s) \leq 2s +\,\text{min-match}(G) - 1.\] Moreover, we show that \[\mathrm{reg}(I(G)^s ) \geq 2s +\,\text{ind-match}_{\{ K_{2}, C_{5}\}} (G) - 2,\] and if ind-match\(_{\{K_{2}, C_{5}\}}(G)\) is an odd integer, then \[\mathrm{reg}(I(G)^s )\geq 2s +\,\text{ind-match}_{\{K_{2}, C_{5}\}}(G) -1.\] As a consequence, we estimate the regularity of powers of edge ideals of Cohen-Macaulay graphs with \(\mathrm{girth}(G)\geq 5\). Furthermore, it is shown that \[\mathrm{reg}(I(G)^s) \leq 2s + \,\text{ord-match}(G)-1,\] where ord-match\((G)\) denotes the ordered matching number of \(G\).