An Estimator for Matching Size in Low Arboricity Graphs with Two Applications

Hossein Jowhari

In this paper, we present a new simple degree-based estimator for the size of maximum matching in bounded arboricity graphs. When the arboricity of the graph is bounded by $\alpha$, the…