Neil Robertson

Minor relations for directed graphs

Abstract for the Special Combinatorics Seminar
Friday, April 23, 1999

The beginning of a general theory of digraph minors is struggling to appear. What are the primary inclusion relations? What structure theory reflects tree-width and universal surface structure? Where does well-quasi-ordering come into the picture? Are there interesting algorithmical decision problems that are not NP hard? Is there any prospect of a coherent body of theorems central to directed graphs? Some formal and informal reflections on these questions (representing the graph minor people) will be the subject matter of this talk.