4 citations · 18 across the 31 of their papers we have counts for
9 papers · 1 filter
Clique-Width for Graph Classes Closed under Complementation
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson +3
Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite)…
Perfect Edge Domination: Hard and Solvable Cases
Min Chih Lin, Vadim Lozin, Veronica A. Moyano +1
Let be an undirected graph. An edge of dominates itself and all edges adjacent to it. A subset of edges of is an edge dominating set of , if every edge of the g…
Upper Domination: towards a dichotomy through boundary properties
Hassan AbouEisha, Shahid Hussain, Vadim Lozin +3
An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally N…
Graph parameters, Ramsey theory and the speed of hereditary properties
Vadim Lozin
The speed of a hereditary property is the number of -vertex labelled graphs in . It is known that the rates of growth of constitute discrete layers and the sp…
More results on weighted independent domination
Vadim Lozin, Dmitriy Malyshev, Raffaele Mosca +1
Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in th…
Dominating induced matchings in graphs containing no long claw
Alain Hertz, Vadim Lozin, Bernard Ries +2
An induced matching in a graph is dominating if every edge not in shares exactly one vertex with an edge in . The dominating induced matching problem (also known as…
Well-quasi-ordering does not imply bounded clique-width
Vadim Lozin, Igor Razgon, Viktor Zamaraev
We present a hereditary class of graphs of unbounded clique-width which is well-quasi-ordered by the induced subgraph relation. This result provides a negative answer to the questi…
Combinatorics and algorithms for augmenting graphs
Konrad K. Dabrowski, Dominique de Werra, Vadim V. Lozin +1
The notion of augmenting graphs generalizes Berge's idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is…
Polynomial-time algorithm for vertex k-colorability of P_5-free graphs
Marcin Kaminski, Vadim Lozin
We give the first polynomial-time algorithm for coloring vertices of P_5-free graphs with k colors. This settles an open problem and generalizes several previously known results.