Discrete Mathematics and Optimization Seminar

Princeton University
Monday November 15th at 4.30pm
Burnside 1205

Title. Rank-width and Well-quasi-ordering.

Abstract. For a graph G=(V,E) and v in V, a local complementation at v is an operation that replaces the neighborhood of v by its complement. A
graph H is called a vertex-minor of G if H can be obtained by applying a sequence of vertex-deletions and local complementations. It will be
shown that for fixed k, if {G_1,G_2,...} is an infinite sequence of graphs of rank-width (or clique-width) at most k, then there exist i
less than j such that G_i is isomorphic to a vertex-minor of G_j. The proof is very similar to proofs of well-quasi-ordering theorem of
graphs by Robertson and Seymour and well-quasi-ordering theorem of binary matroids (or representable matroids over a fixed finite field)
by Geelen, Gerards, and Whittle. In fact, well-quasi-ordering theorem of binary matroids is implied from our theorem.