Seminar

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.
Organizers
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU

Program
Contact

Klas Markström

klas.markstrom@math.umu.se

Other
information

For practical matters at the Institute, send an e-mail to secretary@mittag-leffler.se