20 citations · 146 across the 41 of their papers we have counts for
34 papers · 1 filter
On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
Vahan Mkrtchyan, Garik Petrosyan
In the classical partial vertex cover problem, we are given a graph and two positive integers and . The goal is to check whether there is a subset of of size at…
On sublinear approximations for the Petersen coloring conjecture
Davide Mattiolo, Giuseppe Mazzuoccolo, Vahan Mkrtchyan
If is a function, then let us say that is sublinear if \[\lim_{n\rightarrow +\infty}\frac{f(n)}{n}=0.\] If is a cubic graph and $…
Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
Hanna Furmańczyk, Vahan Mkrtchyan
An equitable coloring of a graph is a (proper) vertex-coloring of , such that the sizes of any two color classes differ by at most one. In this paper, we consider the…
Sublinear bounds for nullity of flows and approximating Tutte's flow conjectures
Vahan Mkrtchyan
A function is sublinear, if \[\lim_{x\rightarrow +\infty}\frac{f(x)}{x}=0.\] If is an Abelian group, is a graph and is an -flow in , then let $…
Vizing-Goldberg type bounds for the equitable chromatic number of block graphs
Janusz Dybizbański, Hanna Furmańczyk, Vahan Mkrtchyan
An equitable coloring of a graph is a proper vertex coloring of such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that…
Parameterized algorithms for Partial vertex covers in bipartite graphs
Vahan Mkrtchyan, Garik Petrosyan, K. Subramani
In the weighted partial vertex cover problem (WPVC), we are given a graph , cost function , profit function , and positive integers …
On the fixed-parameter tractability of the maximum connectivity improvement problem
Federico Corò, Gianlorenzo D'Angelo, Vahan Mkrtchyan
In the Maximum Connectivity Improvement (MCI) problem, we are given a directed graph and an integer and we are asked to find new edges to be added to in order…
Normal -edge-colorings of a family of Loupekhine snarks
Luca Ferrarini, Giuseppe Mazzuoccolo, Vahan Mkrtchyan
In a proper edge-coloring of a cubic graph an edge is called poor or rich, if the set of colors of the edges incident to and contains exactly three or five colors, res…
Assigning tasks to agents under time conflicts: a parameterized complexity approach
Alessandro Aloisio, Vahan Mkrtchyan
We consider the problem of assigning tasks to agents under time conflicts, with applications also to frequency allocations in point-to-point wireless networks. In particular, we ar…
Normal 6-edge-colorings of some bridgeless cubic graphs
Giuseppe Mazzuoccolo, Vahan Mkrtchyan
In an edge-coloring of a cubic graph, an edge is poor or rich, if the set of colors assigned to the edge and the four edges adjacent it, has exactly five or exactly three distinct…
and -colorings of cubic graphs
Anush Hakobyan, Vahan Mkrtchyan
If and are two cubic graphs, then an -coloring of is a proper edge-coloring with edges of , such that for each vertex of , there is a vertex of …
A tight lower bound for the hardness of clutters
Vahan Mkrtchyan, Hovhannes Sargsyan
A {\it clutter} (or {\it antichain} or {\it Sperner family}) is a pair , where is a finite set and is a family of subsets of none of which is a subset of ano…
On maximum -edge-colorable subgraphs of bipartite graphs
Liana Karapetyan, Vahan Mkrtchyan
If , then a -edge-coloring of a graph is an assignment of colors to edges of from the set of colors, so that adjacent edges receive different colors. A -…
On two consequences of Berge-Fulkerson conjecture
Vahan V. Mkrtchyan, Gagik N. Vardanyan
The classical Berge-Fulkerson conjecture states that any bridgeless cubic graph admits a list of six perfect matchings such that each edge of belongs to two of the perfect…
Normal edge-colorings of cubic graphs
Giuseppe Mazzuoccolo, Vahan Mkrtchyan
A normal -edge-coloring of a cubic graph is an edge-coloring with colors having the additional property that when looking at the set of colors assigned to any edge and t…
Graphs, Disjoint Matchings and Some Inequalities
Lianna Hambardzumyan, Vahan Mkrtchyan
For and a graph let denote the size of a maximum -edge-colorable subgraph of . Mkrtchyan, Petrosyan and Vardanyan proved that $ν_2(G)\geq \frac45\cdot…
Equitable Colorings of Corona Multiproducts of Graphs
Hanna Furmañczyk, Marek Kubale, Vahan V. Mkrtchyan
A graph is equitably -colorable if its vertices can be partitioned into independent sets in such a way that the number of vertices in any two sets differ by at most one. The…
A remark on Petersen coloring conjecture of Jaeger
Vahan V. Mkrtchyan
If and are two cubic graphs, then we write , if admits a proper edge-coloring with edges of , such that for each vertex of , there is a vertex $…
On strongly spanning -edge-colorable subgraphs
Vahan V. Mkrtchyan, Gagik N. Vardanyan
A subgraph of a multigraph is called strongly spanning, if any vertex of is not isolated in , while it is called maximum -edge-colorable, if is proper -edg…
A note on triangle-free graphs
Vahan V. Mkrtchyan, Petros A. Petrosyan
We show that if is a simple triangle-free graph with vertices, without a perfect matching, and having a minimum degree at least , then is isomorphi…
Bricks and conjectures of Berge, Fulkerson and Seymour
Vahan Mkrtchyan, Eckhard Steffen
An -graph is an -regular graph where every odd set of vertices is connected by at least edges to the rest of the graph. Seymour conjectured that any -graph is -ed…
Measures of edge-uncolorability
Vahan Mkrtchyan, Eckhard Steffen
The resistance of a graph is the minimum number of edges that have to be removed from to obtain a graph which is -edge-colorable. The paper relates the resista…
Maximum -edge-colorable subgraphs of class II graphs
Vahan V. Mkrtchyan, Eckhard Steffen
A graph is class II, if its chromatic index is at least . Let be a maximum -edge-colorable subgraph of . The paper proves best possible lower bounds for $\frac{|…
On disjoint matchings in cubic graphs: maximum 2- and 3-edge-colorable subgraphs
Davit Aslanyan, Vahan V. Mkrtchyan, Samvel S. Petrosyan +1
We show that any factor of a cubic graph can be extended to a maximum edge-colorable subgraph. We also show that the sum of sizes of maximum and edge-colorable sub…