4 citations · 18 across the 31 of their papers we have counts for
28 papers · 1 filter
Graph parameters, implicit representations and factorial properties
Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas +2
How to efficiently represent a graph in computer memory is a fundamental data structuring question. In the present paper, we address this question from a combinatorial point of vie…
Functionality of box intersection graphs
Clément Dallard, Vadim Lozin, Martin Milanič +2
Functionality is a graph complexity measure that extends a variety of parameters, such as vertex degree, degeneracy, clique-width, or twin-width. In the present paper, we show that…
A dichotomy for graphs of bounded degeneracy
A. Atminas, V. Lozin
We prove that the degeneracy of graphs in a hereditary class defined by a finite set S of forbidden induced subgraphs is bounded if and only if S includes a complete graph, a compl…
The treewidth and pathwidth of graph unions
Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz +3
Given two -vertex graphs and of bounded treewidth, is there an -vertex graph of bounded treewidth having subgraphs isomorphic to and ? Our main res…
Letter graphs and geometric grid classes of permutations
Bogdan Alecu, Robert Ferguson, Mamadou Moustapha Kanté +3
We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both…
Understanding lettericity I: a structural hierarchy
Bogdan Alecu, Vadim Lozin
Lettericity is a graph parameter introduced by Petkovšek in 2002 in order to study well-quasi-orderability under the induced subgraph relation. In the world of permutations, geomet…
Combinatorics and algorithms for quasi-chain graphs
Bogdan Alecu, Aistis Atminas, Vadim Lozin +1
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width…
Tree-width dichotomy
Vadim Lozin, Igor Razgon
We prove that the tree-width of graphs in a hereditary class defined by a finite set of forbidden induced subgraphs is bounded if and only if includes a complete graph, a c…
Critical properties of bipartite permutation graphs
Bogdan Alecu, Vadim Lozin, Dmitriy Malyshev
The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique- and rank-width of gra…
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…
Graph functionality
Bogdan Alecu, Aistis Atminas, Vadim Lozin
Let be a graph and its adjacency matrix. We say that a vertex is a function of vertices if there exists a Boolean function of $…
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…
Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes
Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma
Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamar…
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…
Infinitely many minimal classes of graphs of unbounded clique-width
A. Collins, J. Foniok, N. Korpelainen +2
The celebrated theorem of Robertson and Seymour states that in the family of minor-closed graph classes, there is a unique minimal class of graphs of unbounded tree-width, namely,…
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma
Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev rece…
The structure and the number of -free bipartite graphs
Vadim Lozin, Viktor Zamaraev
We show that the number of labelled -free bipartite graphs with vertices grows as . This resolves an open problem posed by Allen [P. Allen, Forbidden induced bip…
Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
A. Atminas, R. Brignall, V. Lozin +1
We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bicha…
Implicit Representations and Factorial Properties of Graphs
Aistis Atminas, Andrew Collins, Vadim Lozin +1
The idea of implicit representation of graphs was introduced in [S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. Discrete Mathematics, 5 (1992) 596--603]…
Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
Aistis Atminas, Vadim V. Lozin, Igor Razgon
Recently, Daligault, Rao and Thomassé asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. There are two…
Deciding the Bell number for hereditary graph properties
Aistis Atminas, Andrew Collins, Jan Foniok +1
The paper [J. Balogh, B. Bollobás, D. Weinreich, A jump to the Bell number for hereditary graph properties, J. Combin. Theory Ser. B 95 (2005) 29--48] identifies a jump in the spee…
Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
Aistis Atminas, Robert Brignall, Nicholas Korpelainen +2
We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting and…
Universal graphs and universal permutations
Aistis Atminas, Sergey Kitaev, Vadim V. Lozin +1
Let be a family of graphs and the set of -vertex graphs in . A graph containing all graphs from as induced subgraphs is called -universal for …