This thesis aims to extend some of the results of the Graph Minors Project of Robertson and Seymour to "group-labelled graphs". Let $\Gamma$ be a group. A $\Gamma$-labelled graph is an oriented graph with its edges labelled from $\Gamma$, and is thus a generalization of a signed graph. Our primary result is a generalization of the main result from Graph Minors XIII. For any finite abelian group $\Gamma$, and any fixed $\Gamma$-labelled graph $H$, we present a polynomial-time algorithm that determines if an input $\Gamma$-labelled graph $G$ has an $H$-minor. The correctness of our algorithm relies on much of the machinery developed throughout the graph minors papers. We therefore hope it can serve as a reasonable introduction to the subject. Remarkably, Robertson and Seymour also prove that for any sequence $G_1, G_2, \dots$ of graphs, there exist indices $i<j$ such that $G_i$ is isomorphic to a minor of $G_j$. Geelen, Gerards and Whittle recently announced a proof of the analogous result for $\Gamma$-labelled graphs, for $\Gamma$ finite abelian. Together with the main result of this thesis, this implies that membership in any minor closed class of $\Gamma$-labelled graphs can be decided in polynomial-time. This also has some implications for well-quasi-ordering certain classes of matroids, which we discuss.

This thesis aims to extend some of the results of the Graph Minors Project of Robertson and Seymour to "group-labelled graphs". Let $\Gamma$ be a group. A $\Gamma$-labelled graph is an oriented graph with its edges labelled from $\Gamma$, and is thus a generalization of a signed graph. Our primary result is a generalization of the main result from Graph Minors XIII. For any finite abelian group $\Gamma$, and any fixed $\Gamma$-labelled graph $H$, we present a polynomial-time algorithm that determines if an input $\Gamma$-labelled graph $G$ has an $H$-minor. The correctness of our algorithm relies on much of the machinery developed throughout the graph minors papers. We therefore hope it can serve as a reasonable introduction to the subject. Remarkably, Robertson and Seymour also prove that for any sequence $G_1, G_2, \dots$ of graphs, there exist indices $i<j$ such that $G_i$ is isomorphic to a minor of $G_j$. Geelen, Gerards and Whittle recently announced a proof of the analogous result for $\Gamma$-labelled graphs, for $\Gamma$ finite abelian. Together with the main result of this thesis, this implies that membership in any minor closed class of $\Gamma$-labelled graphs can be decided in polynomial-time. This also has some implications for well-quasi-ordering certain classes of matroids, which we discuss.

No description available.

We first prove a ``non-embeddable extensions' theorem for polyhedral graph embeddings. Let G be a ``weakly 4-connected' planar graph. We describe a set of constructions that produce a finite list of non-planar graphs, each having a minor isomorphic to G, such that every non-planar weakly 4-connected graph H that has a minor isomorphic to G has a minor isomorphic to one of the graphs in the list. The theorem is more general and applies in particular to polyhedral embeddings in any surface. We discuss an approach to proving Jorgensen's conjecture, which states that if G is a 6-connected graph with no K_6 minor, then it is apex, that is, it has a vertex v such that deleting v yields a planar graph. We relax the condition of 6-connectivity, and prove Jorgensen's conjecture for a certain sub-class of these graphs. We prove that every graph embedded in the Klein bottle with representativity at least 4 has a K_6 minor. Also, we prove that every ``locally 5-connected' triangulation of the torus, with one exception, has a K_6 minor. (Local 5-connectivity is a natural notion of local connectivity for a surface embedding.) The above theorem uses a locally 5-connected version of the well-known splitter theorem for triangulations of any surface. We conclude with a theoretically optimal algorithm for the following graph connectivity problem. A shredder in an undirected graph is a set of vertices whose removal results in at least three components. A 3-shredder is a shredder of size three. We present an algorithm that, given a 3-connected graph, finds its 3-shredders in time proportional to the number of vertices and edges, when implemented on a RAM (random access machine).

Extremal Functions for Graph Linkages and Rooted Minors Paul Wollan 137 pages Directed by: Robin Thomas A graph G is k-linked if for any 2k distinct vertices s_1,..., s_k,t_1,..., t_k there exist k vertex disjoint paths P_1,...,P_k such that the endpoints of P_i are s_i and t_i. Determining the existence of graph linkages is a classic problem in graph theory with numerous applications. In this thesis, we examine sufficient conditions that guarantee a graph to be k-linked and give the following theorems. (A) Every 2k-connected graph on n vertices with 5kn edges is k-linked. (B) Every 6-connected graph on n vertices with 5n-14 edges is 3-linked. The proof method for Theorem (A) can also be used to give an elementary proof of the weaker bound that 8kn edges suffice. Theorem (A) improves upon the previously best known bound due to Bollobas and Thomason stating that 11kn edges suffice. The edge bound in Theorem (B) is optimal in that there exist 6-connected graphs on n vertices with 5n-15 edges that are not 3-linked. The methods used prove Theorems (A) and (B) extend to a more general structure than graph linkages called rooted minors. We generalize the proof methods for Theorems (A) and (B) to find edge bounds for general rooted minors, as well as finding the optimal edge bound for a specific family of bipartite rooted minors. We conclude with two graph theoretical applications of graph linkages. The first is to the problem of determining when a small number of vertices can be used to cover all the odd cycles in a graph. The second is a simpler proof of a result of Boehme, Maharry and Mohar on complete minors in huge graphs of bounded tree-width.

Hadwiger's Conjecture from 1943 states that every graph with no Kt minor is (t-1)-colorable; it remains wide open for t ≥ 7. For positive integers t and s, let Kt-s denote the family of graphs obtained from the complete graph Kt by removing s edges. We say that a graph has no Kt-s minor if it has no H minor for every H in Kt-s. In 1971, Jakobsen proved that every graph with no K7-2 minor is 6-colorable. In this dissertation, we first study the extremal functions for K8-4 minors, K9-6 minors, and K10-12 minors. We show that every graph on n ≥ 9 vertices with at least 4.5n-12 edges has a K8-4 minor, every graph on n ≥ 9 vertices with at least 5n-14 edges has a K9-6 minor, and every graph on n ≥ 10 vertices with at least 5.5n-17.5 edges has a K10-12 minor. We then prove that every graph with no K8-4 minor is 7-colorable, every graph with no K9-6 minor is 8-colorable, and every graph with no K10-12 minor is 9-colorable. The proofs use the extremal functions as well as generalized Kempe chains of contraction-critical graphs obtained by Rolek and Song and a method for finding minors from three different clique subgraphs, originally developed by Robertson, Seymour, and Thomas in 1993 to prove Hadwiger's Conjecture for t = 6. Our main results imply that H-Hadwiger's Conjecture is true for each graph H on 8 vertices that is a subgraph of every graph in K8-4, each graph H on 9 vertices that is a subgraph of every graph in K9-6, and each graph H on 10 vertices that is a subgraph of every graph in K10-12.

In this dissertation, a problem related to Hadwiger's conjecture has been studied. We first proved a conjecture of Jakobsen from 1983 which states that every simple graphs on $n$ vertices and at least (11n-35)/2 edges either has a minor isomorphic to K_8 with one edge deleted or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2} and/or K_7 by identifying cliques of size five. We then studied the extremal functions for complete minors. We proved that every simple graph on nge9 vertices and at least 7n-27 edges either has a minor, or is isomorphic to K_{2, 2, 2, 3, 3}, or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2, 2} by identifying cliques of size six. This result extends Mader's theorem on the extremal function for K_p minors, where ple7. We discussed the possibilities of extending our methods to K_{10} and K_{11} minors. We have also found the extremal function for K_7 plus a vertex minor.

Conjectured in 1943, Hadwiger’s conjecture is one of the most challenging open problems in graph theory. Hadwiger’s conjecture states that if the chromatic number of a graph G is k, then G has a clique minor of size at least k. In this thesis, we give motivation for attempting Hadwiger’s conjecture for circular arc graphs and also prove the conjecture for proper circular arc graphs. Circular arc graphs are graphs whose vertices can be represented as arcs on a circle such that any two vertices are adjacent if and only if their corresponding arcs intersect. Proper circular arc graphs are a subclass of circular arc graphs that have a circular arc representation where no arc is completely contained in any other arc. It is interesting to study Hadwiger’s conjecture for circular arc graphs as their clique minor cannot exceed beyond a constant factor of its chromatic number as We show in this thesis. Our main contribution is the proof of Hadwiger’s conjecture for proper circular arc graphs. Also, in this thesis we give an analysis and some basic results on Hadwiger’s conjecture for circular arc graphs in general.