Well-quasi-ordering of directed graphs

Graph Theory Seminar
Thursday, September 19, 2013 - 12:05
1 hour (actually 50 minutes)
Skiles 005
School of Mathematics, Georgia Tech and University of Rome, Italy
While Robertson and Seymour showed that graphs are well-quasi-ordered under the minor relation, it is well known that directed graphs are not. We will present an exact characterization of the minor-closed sets of directed graphs which are well-quasi-ordered. This is joint work with M. Chudnovsky, S. Oum, I. Muzi, and P. Seymour.