RUS  ENG
Полная версия
ЖУРНАЛЫ // Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica // Архив

Bul. Acad. Ştiinţe Repub. Mold. Mat., 2023, номер 3, страницы 26–36 (Mi basm599)

Graphs, disjoint matchings and some inequalities

Lianna Hambardzumyana, Vahan Mkrtchyanb

a Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, 0025, Armenia
b Gran Sasso Science Institute, School of Advanced Studies, L'Aquila, Italy

Аннотация: 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}$ [13]. 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.

Ключевые слова и фразы: bipartite graph, tree, unicyclic graph, edge-coloring, parsimonious edge-coloring.

MSC: 05C15, 05C70

Поступила в редакцию: 28.02.2020

DOI: 10.56415/basm.y2023.i3.p26



© МИАН, 2024