Zobrazeno 1 - 10
of 337
pro vyhledávání: '"Lozin, Vadim"'
Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies th
Externí odkaz:
http://arxiv.org/abs/2402.12559
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 view. A representation of an $n$-vertex graph $G$ is called implicit if i
Externí odkaz:
http://arxiv.org/abs/2303.04453
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 functionality is bounded for box intersection graphs in $\mathbb{R}^1
Externí odkaz:
http://arxiv.org/abs/2301.09493
Autor:
Lozin, Vadim, Martin, Barnaby, Pandey, Sukanya, Paulusma, Daniel, Siggers, Mark, Smith, Siani, van Leeuwen, Erik Jan
For a fixed set ${\cal H}$ of graphs, a graph $G$ is ${\cal H}$-subgraph-free if $G$ does not contain any $H \in {\cal H}$ as a (not necessarily induced) subgraph. A recently proposed framework gives a complete classification on ${\cal H}$-subgraph-f
Externí odkaz:
http://arxiv.org/abs/2211.14214
Autor:
Alecu, Bogdan, Lozin, Vadim, Quiroz, Daniel A., Rabinovich, Roman, Razgon, Igor, Zamaraev, Viktor
Given two $n$-vertex graphs $G_1$ and $G_2$ of bounded treewidth, is there an $n$-vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_1$ and $G_2$? Our main result is a negative answer to this question, in a strong sense: we show
Externí odkaz:
http://arxiv.org/abs/2202.07752
Autor:
Alecu, Bogdan, Ferguson, Robert, Kanté, Mamadou Moustapha, Lozin, Vadim, Vatter, Vincent, Zamaraev, Viktor
We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their res
Externí odkaz:
http://arxiv.org/abs/2107.03447
Autor:
Alecu, Bogdan, Lozin, Vadim
Lettericity is a graph parameter introduced by Petkov\v{s}ek in 2002 in order to study well-quasi-orderability under the induced subgraph relation. In the world of permutations, geometric griddability was independently introduced in 2013 by Albert, A
Externí odkaz:
http://arxiv.org/abs/2106.03267
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, implicit representation, well-quasi-ordering by induced subgraphs, e
Externí odkaz:
http://arxiv.org/abs/2104.04471
Autor:
Lozin, Vadim, Razgon, Igor
We prove that the tree-width of graphs in a hereditary class defined by a finite set $F$ of forbidden induced subgraphs is bounded if and only if $F$ includes a complete graph, a complete bipartite graph, a tripod (a forest in which every connected c
Externí odkaz:
http://arxiv.org/abs/2012.01115
Autor:
Lozin, Vadim, Zamaraev, Viktor
Publikováno v:
In Journal of Combinatorial Theory, Series A February 2024 202
