Graphs, Disjoint Matchings and Some Inequalities

A graph G is k-edge-colorable if the edges of G can be assigned a color from 1,. . . , k so that adjacent edges of G receive different colors. A maximum kedge-colorable subgraph of G is a k-edge-colorable subgraph of G containing maximum number of edges. For k ≥ 1 and a graph G, let νk (G) denote the number of edges in a maximum k-edge-colorable subgraph of G. In 2010 Mkrtchyan, Petrosyan and Vardanyan proved that if G is a cubic graph, then ν2 (G) ≤ |V (G) |+2·ν3 (G) 4 13. For cubic graphs containing a perfect matching, in particular, for bridgeless cubic graphs, this inequality can be stated as ν2 (G) ≤ ν1 (G) +ν3 (G) 2. One may wonder whether there are other well-known graph classes, where a similar result can be obtained. In this work, we prove lower bounds for νk (G) in terms of νk−1 (G) +νk+1 (G) 2 for k ≥ 2 and graphs G containing at most 1 cycle. We also present the corresponding conjectures for nearly bipartite graphs.