Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 6 of 6 for “"unavoidable minors"”.
-
Connectivity, tree-decompositions and unavoidable-minors
… the very general, yet wildly qualitative, Graph Minors Structure Theorem. This thesis introduces a refinement of the notion of tree-width. Tree-width is a measure of how “tree-like” a graph is. Essentially, a graph is tree-like if it can be decomposed across a collection of non-crossing …
-
Unavoidable minors in graphs and matroids
… we ensure the presence of more highly structured minors. In particular, for all positive integers k, every 2-connected graph G has a series minor isomorphic to a k-edge cycle or K_{2,k}. In 1993, Oxley, Oporowski, and Thomas extended this result to 3- and internally 4-connected graphs identifying …
-
Unavoidable Minors of Large 5-Connected Graphs
This thesis shows that, for every positive integer $n \geq 5$, there exists a positive integer $N$ such that every $5-$connected graph with at least $N$ vertices has a minor isomorphic to one of thirty explicitly defined $5-$connected graphs $H_1(n), ..., H_{30}(n)$, each with at least $n$ vertices.
-
Forbidden Induced Restrictions and Unavoidable Minors in Matroids
Targets are matroids that arise from a nested sequence of flats in a projective geometry. This class of matroids was introduced by Nelson and Nomoto, who found the forbidden induced restrictions for binary targets. In this dissertation, their result is generalized to targets arising from projective …
-
Extremal Problems in Matroid Connectivity
… the containment of small subsets in 3-connected minors from a given list of 3-connected matroids. Bixby’s Lemma is a well-known inductive tool in matroid theory that says that each element in a 3-connected matroid can be deleted or contracted to obtain a matroid that is 3-connected up to minimal …
-
On Matroid and Polymatroid Connectivity
Matroids were introduced in 1935 by Hassler Whitney to provide a way to abstractly capture the dependence properties common to graphs and matrices. One important class of matroids arises by taking as objects some finite collection of one-dimensional subspaces of a vector space. If, instead, one …