4 citations · 18 across the 31 of their papers we have counts for
39 papers
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…