On maximum $k$-edge-colorable subgraphs of bipartite graphs

Abstract

If $k\ge 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\ge 0$, let ${\nu }_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 ${\nu }_2(G)\le \frac{|V|+2{\nu }_3(G)}{4}$. This result implies that if the cubic graph $G$ contains a perfect matching, in particular when it is bridgeless, then ${\nu }_2(G)\le \frac{{\nu }_1(G)+{\nu }_3(G)}{2}$. One may wonder whether there are other interesting graph-classes, where a relation between ${\nu }_2(G)$ and $\frac{{\nu }_1(G)+{\nu }_3(G)}{2}$ can be proved. Related with this question, in this paper we show that ${\nu }_k(G)\ge \frac{{\nu }_{k-i}(G)+{\nu }_{k+i}(G)}{2}$ for any bipartite graph $G$, $k\ge 0$ and $i=0,1,...,k$.

arXiv comment11 pages, 1 figure