4 papers · 1 filter
Infinitely many minimal classes of graphs of unbounded clique-width
A. Collins, J. Foniok, N. Korpelainen +2
The celebrated theorem of Robertson and Seymour states that in the family of minor-closed graph classes, there is a unique minimal class of graphs of unbounded tree-width, namely,…
Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
Aistis Atminas, Robert Brignall, Nicholas Korpelainen +2
We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting and…
Linear Clique-Width for Hereditary Classes of Cographs
Robert Brignall, Nicholas Korpelainen, Vincent Vatter
The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contai…
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…