|
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.
Поступила в редакцию: 28.02.2020
Образец цитирования:
Lianna Hambardzumyan, Vahan Mkrtchyan, “Graphs, disjoint matchings and some inequalities”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2023, № 3, 26–36
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/basm599 https://www.mathnet.ru/rus/basm/y2023/i3/p26
|
Статистика просмотров: |
Страница аннотации: | 52 | PDF полного текста: | 11 | Список литературы: | 15 |
|