1 citations · 3 across the 5 of their papers we have counts for
6 papers · 1 filter
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani +2
Let , and , respectively, denote the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph . One can a…
Graph classes with linear Ramsey numbers
Bogdan Alecu, Aistis Atminas, Vadim Lozin +1
The Ramsey number for a class of graphs is the minimum such that every graph in with at least vertices has either a clique of size or an independent…
Linear read-once and related Boolean functions
Vadim Lozin, Igor Razgon, Viktor Zamaraev +2
It is known that a positive Boolean function f depending on n variables has at least n + 1 extremal points, i.e. minimal ones and maximal zeros. We show that f has exactly n + 1 ex…
Letter graphs and geometric grid classes of permutations: characterization and recognition
Bogdan Alecu, Vadim Lozin, Dominique de Werra +1
In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common…
Specifying a positive threshold function via extremal points
Vadim Lozin, Igor Razgon, Viktor Zamaraev +2
An extremal point of a positive threshold Boolean function is either a maximal zero or a minimal one. It is known that if depends on all its variables, then the set of its…
On forbidden induced subgraphs for unit disk graphs
Aistis Atminas, Viktor Zamaraev
A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore admits a characterization in terms of m…