Graphs, Disjoint Matchings and Some Inequalities

Lianna Hambardzumyan ; Vahan Mkrtchyan

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2023), pp. 26-36

Résumé

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 $k$-edge-colorable subgraph of $G$ is a $k$-edge-colorable subgraph of $G$ containing maximum number of edges. For $k \geq 1$ and a graph $G$, let $\nu_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 $\nu_2(G) \leq \frac{|V(G)| + 2\cdot \nu_3(G)}{4}$ [samvel:2010]. For cubic graphs containing a perfect matching, in particular, for bridgeless cubic graphs, this inequality can be stated as $\nu_2(G) \leq \frac{\nu_1(G) + \nu_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 $\nu_k(G)$ in terms of $\frac{\nu_{k-1}(G)+\nu_{k+1}(G)}{2}$ for $k\geq 2$ and graphs $G$ containing at most $1$ cycle. We also present the corresponding conjectures for nearly bipartite graphs.