Discrete Mathematics and Optimization Seminar
SANG-IL OUM |
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.