17 citations · 42 across the 15 of their papers we have counts for
7 papers · 1 filter
Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
Mamadou Mostapha Kanté, Eun Jung Kim, O-joung Kwon +1
Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. How…
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…
Tree pivot-minors and linear rank-width
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~, the class…
Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions
Mamadou Moustapha Kanté, O-joung Kwon
In the companion paper [Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm, Algorithmica 78(1):342--377, 2017], we presented a characterization of the l…
An Upper Bound on the Size of Obstructions for Bounded Linear Rank-Width
Mamadou Moustapha Kanté, O-joung Kwon
We provide a doubly exponential upper bound in on the size of forbidden pivot-minors for symmetric or skew-symmetric matrices over a fixed finite field of linear r…
Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm
Isolde Adler, Mamadou Moustapha Kanté, O-joung Kwon
Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every -vertex dis…
Well-Quasi-Ordering of Matrices under Schur Complement and Applications to Directed Graphs
Mamadou Moustapha Kanté
In [Rank-Width and Well-Quasi-Ordering of Skew-Symmetric or Symmetric Matrices, arXiv:1007.3807v1] Oum proved that, for a fixed finite field , any infinite sequence $M_…