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"”.

  1. 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 …

    waterloo Repository record for Connectivity, tree-decompositions and unavoidable-minors (opens in a new tab)

  2. 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 …

    lsu-thes Repository record for Unavoidable minors in graphs and matroids (opens in a new tab)

  3. 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.

    waterloo Repository record for Unavoidable Minors of Large 5-Connected Graphs (opens in a new tab)

  4. 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 …

    lsu-thes Repository record for Forbidden Induced Restrictions and Unavoidable Minors in Matroids (opens in a new tab)

  5. 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 …

    lsu-thes Repository record for Extremal Problems in Matroid Connectivity (opens in a new tab)

  6. 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 …

    lsu-thes Repository record for On Matroid and Polymatroid Connectivity (opens in a new tab)