Bogdan Alecu

activity

20182024

most citedThe treewidth and pathwidth of graph unions

2 citations · 3 across the 9 of their papers we have counts for

collaborators

10 papers

math.CO2024★ 1 cited

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions

Bogdan Alecu, Mamadou Moustapha Kanté, Vadim Lozin +1

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 w…

math.CO2023

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…

math.CO2022★ 2 cited

The treewidth and pathwidth of graph unions

Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz +3

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 res…

math.CO2021

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…

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…