More graph width parameters and minors: linear rankwidth and vertex minors
Graphs, Hypergraphs, and Computing
27 March 15:30 - 16:30
Andrzej Proskurowski - University of Oregon
We establish the set of minimal forbidden induced subgraphs for the class of graphs having linear rank-width at most 1. From these we derive both the vertex-minor and pivot-minor obstructions for the class. We conclude with a linear-time recognition of the graphs in the class.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU