V. Mkrtchyan

collaborators

4 papers

math.CO2026

Some new results on Sylvester colorings of cubic graphs

Luca Ferrarini, Vahan Mkrtchyan

If $G$ and $H$ are two cubic multi-graphs, then an $H$ -coloring of $G$ is a mapping $f : E (G) \to E (H)$ , such that for every $v \in V (G)$ there is a vertex $x \in V (H)$ , such t…

math.CO2025

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs

Vahan Mkrtchyan

In this paper, we consider the maximum $k$ -edge-colorable subgraph problem. In this problem we are given a graph $G$ and a positive integer $k$ , the goal is to take $k$ matchings o…

math.CO2025

Expanding vertices to triangles in cubic graphs

Giuseppe Mazzuoccolo, Vahan Mkrtchyan

Contraction of triangles is a standard operation in the study of cubic graphs, as it reduces the order of the graph while typically preserving many of its properties. In this paper…

math.CO2025

Three results towards the approximation of special maximum matchings in graphs

Vahan Mkrtchyan

For a graph $G$ define the parameters $ℓ (G)$ and $L (G)$ as the minimum and maximum value of $I^½ (G \ F)$ , where $F$ is a maximum matching of $G$ and $I^½ (G)$ is the matchi…