Bogdan Alecu

activity

20182021

collaborators

6 papers

math.CO2021

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…

math.CO2021

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…

math.CO2020

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…

math.CO2019

Graph classes with linear Ramsey numbers

Bogdan Alecu, Aistis Atminas, Vadim Lozin +1

The Ramsey number $R_{X} (p, q)$ for a class of graphs $X$ is the minimum $n$ such that every graph in $X$ with at least $n$ vertices has either a clique of size $p$ or an independent…

math.CO2018

Graph functionality

Bogdan Alecu, Aistis Atminas, Vadim Lozin

Let $G = (V, E)$ be a graph and $A$ its adjacency matrix. We say that a vertex $y \in V$ is a function of vertices $x_{1}, \dots, x_{k} \in V$ if there exists a Boolean function $f$ of $…

math.CO2018

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…