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