Bounds on maximum -matchings

In this note, we study bounds on the maximum cardinality of a b -matching, where a b -matching is an edge set M b ⊆ E in a graph G = ( V , E ) with the constraint that d M b ( v ) ≤ b for every vertex v . Here d M b ( v ) is the degree of v in the subgraph induced by M b and b ∈ N is a constant. If b = 1 , then b -matchings are ordinary matchings. For the maximum cardinality of an ordinary matching, we derive ν ( G ) ≥ 2 m 3 k − 1 for k ≥ 3 , where ν ( G ) denotes the maximum cardinality of a matching in G , m is the number of edges, and k is the maximum degree of G . This answers an open question proposed by Biedl, Demaine, Duncan, Fleischer and Kobourov [T. Biedl, E. Demaine, C. Duncan, R. Fleischer, S. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math. 285 (1–3) (2004) 7–15]. For the maximum cardinality of a b -matching, we derive ν b ( G ) ν b − 1 ( G ) ≤ 1 + 4 b − 2 3 b 2 − 5 b + 2 for b ≥ 3 , where ν b ( G ) denotes the maximum cardinality of a b -matching in G .