On maximum k-edge-colorable subgraphs of bipartite graphs
share
If k≥ 0, then a k-edge-coloring of a graph G is an assignment of colors to edges of G from the set of k colors, so that adjacent edges receive different colors. A k-edge-colorable subgraph of G is maximum if it is the largest among all k-edge-colorable subgraphs of G. For a graph G and k≥ 0, let ν_k(G) be the number of edges of a maximum k-edge-colorable subgraph of G. In 2010 Mkrtchyan et al. proved that if G is a cubic graph, then ν_2(G)≤|V|+2ν_3(G)/4. This result implies that if the cubic graph G contains a perfect matching, in particular when it is bridgeless, then ν_2(G)≤ν_1(G)+ν_3(G)/2. One may wonder whether there are other interesting graph-classes, where a relation between ν_2(G) and ν_1(G)+ν_3(G)/2 can be proved. Related with this question, in this paper we show that ν_k(G) ≥ν_k-i(G) + ν_k+i(G)/2 for any bipartite graph G, k≥ 0 and i=0,1,...,k.
READ FULL TEXT