V. Mkrtchyan

collaborators

Showing math.COShow all

5 papers · 1 filter

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…

math.CO2024

Non-conflicting no-where zero $Z_{2} \times Z_{2}$ flows in cubic graphs

Vahan Mkrtchyan

Let $Z_{2} \times Z_{2} = {0, I^\pm, I^^{2}, I^\pm + I^^{2}}$ . If $G$ is a bridgeless cubic graph, $F$ is a perfect matching of $G$ and $F$ is the complementary 2-factor of $F$ , then a no-wh…

Some new results on Sylvester colorings of cubic graphs

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

Expanding vertices to triangles in cubic graphs

Three results towards the approximation of special maximum matchings in graphs

Non-conflicting no-where zero Z2​×Z2​ flows in cubic graphs

Non-conflicting no-where zero $Z_{2} \times Z_{2}$ flows in cubic graphs