6 papers
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…
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…
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma
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 rece…
Combinatorics and algorithms for augmenting graphs
Konrad K. Dabrowski, Dominique de Werra, Vadim V. Lozin +1
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…
Implicit Representations and Factorial Properties of Graphs
Aistis Atminas, Andrew Collins, Vadim Lozin +1
The idea of implicit representation of graphs was introduced in [S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. Discrete Mathematics, 5 (1992) 596--603]…
Bipartite Induced Subgraphs and Well-Quasi-Ordering
Nicholas Korpelainen, Vadim V. Lozin
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) b…