Forbidden structures and algorithms in graphs and digraphs

The ingredients of a typical structure theorem in graph theory include a containment relation and a family of graphs F . The theorem then describes the structure of graphs that do not contain (in the sense of the given relation) any member of F . Perhaps the most celebrated structure theorem in graph theory is one due to Robertson and Seymour that describes the structure of all graphs not containing a particular graph as a minor.;The graph minor theorem has many algorithmic consequences. One such consequence is a polynomial-time algorithm to solve the disjoint-paths problem in graphs. At the heart of the algorithm is a structure theorem which says that every graph either has a large grid minor or has bounded tree-width. In this thesis we prove several excluded structure theorems that we similarly use to obtain polynomial-time algorithms. One such theorem says that if a digraph G does not contain a digraph H as an immersion, then the cutwidth of G is bounded by a function of the size of H and the independence number of G. As a consequence of this theorem, we obtain a polynomial-time algorithm to solve the edge-disjoint paths problem in digraphs with bounded independence number.;Another structure theorem proved in this thesis says that if a tournament T does not contain a subdivision of a digraph H as a subgraph, then the pathwidth of the tournament is bounded by a function of the size of H. We use this theorem to obtain a polynomial-time algorithm to test whether a tournament contains a subdivision of a fixed digraph.;In the second part of this thesis, we use a structure theorem of Chudnovsky and Seymour to prove two approximate versions of Hadwiger's conjecture for the class of claw-free graphs. Hadwiger's conjecture says that every graph with chromatic number chi has a clique minor of size chi. We prove that every claw-free graph with chromatic number chi has a clique minor of size 2c3 . We also prove that a claw-free graph with n vertices and independence number alpha has a clique minor of size na .