Source author record

Vadim V. Lozin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Deciding the Bell number for hereditary graph properties

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 speed of hereditary graph properties to the Bell number $B_n$ and provides a partial characterisation of the family of minimal classes whose speed is at least $B_n$ . In the present paper, we give a complete characterisation of this family. Since this family is infinite, the decidability of the problem of determining if the speed of a hereditary property is above or below the Bell number is questionable. We answer this question positively by showing that there exists an algorithm which, given a finite set $\mathcal{F}$ of graphs, decides whether the speed of the class of graphs containing no induced subgraphs from the set $\mathcal{F}$ is above or below the Bell number. For properties defined by infinitely many minimal forbidden induced subgraphs, the speed is known to be above the Bell number.

preprint2016arXiv

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

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 recently showed that this is not true for classes defined by infinitely many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in this case the answer is positive. The conjecture is known to hold for classes of graphs defined by a single forbidden induced subgraph $H$ , as such graphs are well-quasi-ordered and are of bounded clique-width if and only if $H$ is an induced subgraph of $P_4$ . For bigenic classes of graphs, i.e. ones defined by two forbidden induced subgraphs, there are several open cases in both classifications. In the present paper we obtain a number of new results on well-quasi-orderability of bigenic classes, each of which supports the conjecture.

preprint2015arXiv

Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation

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 reasons why this questions is interesting. First, it connects two seemingly unrelated notions. Second, if the question is answered affirmatively, this will have a strong algorithmic consequence. In particular, this will mean (through the use of Courcelle theorem [2]), that any problem definable in Monadic Second Order Logic can be solved in a polynomial time on any class well-quasi-ordered by the induced subgraph relation. In the present paper, we answer this question affirmatively for graphs without large bicliques. Thus the above algorithmic consequence is true, for example, for classes of graphs of bounded degree.

preprint2014arXiv

Combinatorics and algorithms for augmenting graphs

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 a special case of the more general maximum independent set (MIS) problem. Recently, the augmenting graph approach has been successfully applied to solve MIS in various other special cases. However, our knowledge of augmenting graphs is still very limited, and we do not even know what the minimal infinite classes of augmenting graphs are. In the present paper, we find an answer to this question and apply it to extend the area of polynomial-time solvability of the maximum independent set problem.

preprint2013arXiv

Universal graphs and universal permutations

Let $X$ be a family of graphs and $X_n$ the set of $n$ -vertex graphs in $X$ . A graph $U^{(n)}$ containing all graphs from $X_n$ as induced subgraphs is called $n$ -universal for $X$ . Moreover, we say that $U^{(n)}$ is a proper $n$ -universal graph for $X$ if it belongs to $X$ . In the present paper, we construct a proper $n$ -universal graph for the class of split permutation graphs. Our solution includes two ingredients: a proper universal 321-avoiding permutation and a bijection between 321-avoiding permutations and symmetric split permutation graphs. The $n$ -universal split permutation graph constructed in this paper has $4n^3$ vertices, which means that this construction is order-optimal.

preprint2010arXiv

Bipartite Induced Subgraphs and Well-Quasi-Ordering

We study bipartite graphs partially ordered by the induced subgraph relation. Our goal is to distinguish classes of bipartite graphs which are or are not well-quasi-ordered (wqo) by this relation. Answering an open question from \cite{Ding92}, we prove that $P_7$ -free bipartite graphs are not wqo. On the other hand, we show that $P_6$ -free bipartite graphs are wqo. We also obtain some partial results on subclasses of bipartite graphs defined by forbidding more than one induced subgraph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.