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 20 of 33 for “"minor-closed"”.

  1. Induced-minor-closed classes of matroids

    … We show that this class of matroids is closed under induced minors and characterize the class by its forbidden induced minors, noting that the case when q=2 is distinctive. Additionally, we show that the class of GF(2)-chordal matroids coincides with the class of binary matroids that …

    lsu-thes Repository record for Induced-minor-closed classes of matroids (opens in a new tab)

  2. Splittability within minor-closed classes to graphs of low maximum degree

    Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K$_5$ ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K$_5$ ως έλασσον μέγιστου βαθμού 22, και ρώτησε αν αυτός είναι …

    athens Repository record for Splittability within minor-closed classes to graphs of low maximum degree (opens in a new tab)

  3. Excluded minors for nearly-paving matroids

    … or not M belongs to a given class. An excluded minor of a minor-closed class is a matroid N that is, in a sense, minimal with respect to not being in the minor-closed class. An attractive way to characterize a minor-closed class of matroids is to determine the complete list of excluded minors …

    csusb Repository record for Excluded minors for nearly-paving matroids (opens in a new tab)

  4. Exploring Matroid Minors

    … For special classes of matroids that are minor-closed, this question is commonly answered by determining a complete list of matroids that are not in the class but have the property that each of their proper minors is in the class; that is, minor-minimal matroids that are not in the …

    csusb Repository record for Exploring Matroid Minors (opens in a new tab)

  5. Exponentially Dense Matroids

    … to the maximum density of rank-n matroids in a minor-closed class. Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth rate function is defined by h_M(n) = max(|N| : N ∈ M simple, r(N) ≤ n). The Growth Rate Theorem, due to Geelen, Kabell, …

    waterloo Repository record for Exponentially Dense Matroids (opens in a new tab)

  6. Excluded-minor characterization of apex-outerplanar graphs

    … known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K_4 and K_{2,3}. The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We provide the complete list of 57 excluded minors for this …

    lsu-thes Repository record for Excluded-minor characterization of apex-outerplanar graphs (opens in a new tab)

  7. Book embeddings of graphs

    … of Robertson and Seymour to show that for every minor-closed class of graphs, other than the class of all graphs, there is a number k such that every member of the class can be embedded in a book with k pages. Book embeddings of graphs with relation to surfaces, vertex extensions, clique-sums and …

    lsu-thes Repository record for Book embeddings of graphs (opens in a new tab)

  8. Quadratically Dense Matroids

    … the maximum density of rank-$n$ matroids in a minor-closed class. The extremal function of a non-empty minor-closed class $\mathcal M$ of matroids which excludes a rank-2 uniform matroid is defined by $$h_{\mathcal M}(n)=\max(|M|\colon M\in \mathcal M \text{ is simple, and } r(M)\le n).$$ The …

    waterloo Repository record for Quadratically Dense Matroids (opens in a new tab)

  9. Connectivity and related properties for graph classes

    … new technical results needed later, we look at minor-closed, labelled classes of graphs. The excluded minors are always assumed to be connected, which is equivalent to the class A being decomposable - a graph is in A if and only if every component of the graph is in A. When A is minor-closed, …

    oxford Repository record for Connectivity and related properties for graph classes (opens in a new tab)

  10. Efficient algorithms in quantum query complexity

    … we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be …

    waterloo Repository record for Efficient algorithms in quantum query complexity (opens in a new tab)

  11. Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor

    … that every graph that excludes 𝐾₅ and 𝐾₃,₃ as minors has rectilinear crossing number 0. We are interested in discovering other proper minor-closed families of graphs which admit strong upper bounds on their rectilinear crossing numbers. Unfortunately, it is known that the crossing number of …

    ottawa-retro Repository record for Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor (opens in a new tab)

  12. Linearly-dense classes of matroids with bounded branch-width

    Let $M$ be a non-empty minor-closed class of matroids with bounded branch-width that does not contain arbitrarily large simple rank-$2$ matroids. For each non-negative integer $n$ we denote by $ex(n)$ the size of the largest simple matroid in $M$ that has rank at most $n$. We prove that there exist …

    waterloo Repository record for Linearly-dense classes of matroids with bounded branch-width (opens in a new tab)

  13. Local properties of graphs with large chromatic number

    … a conjecture of Geelen that every proper vertex-minor-closed class of graphs is $\chi$-bounded.

    waterloo Repository record for Local properties of graphs with large chromatic number (opens in a new tab)

  14. On The Density of Binary Matroids Without a Given Minor

    … can a simple binary matroid with no $\PG(t,2)$-minor have? This is a natural analogue of questions asked about the density of graphs in minor-closed classes. We will answer this question by finding the eventual growth rate function of the class of matroids with no $\PG(t,2)$-minor, for any $t\ge …

    waterloo Repository record for On The Density of Binary Matroids Without a Given Minor (opens in a new tab)

  15. Characterizations of Some Classes of Graphs That Are Nearly Series-Parallel

    … that do not have the complete graph K4 as a minor. This dissertation considers a class M1 of graphs that are close to being series-parallel. In particular, every member of the class has the property that one can obtain a series-parallel graph by adding a new edge and contracting it out, or by …

    lsu-thes Repository record for Characterizations of Some Classes of Graphs That Are Nearly Series-Parallel (opens in a new tab)

  16. Dissecting an integer polymatroid

    … of the independent set polytopes of the minors of ρ. To better understand the interior of this polytope, we endow a structure on this polytope which relates to the polymatroid operation of compression and the k-natural matroid of ρ. The latter can be intuited as follows: if we think of a …

    cornell Repository record for Dissecting an integer polymatroid (opens in a new tab)

  17. Connectivity, tree-decompositions and unavoidable-minors

    … handful of exact structure theorems known for minor-closed classes of graphs, and 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 …

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

  18. Morphisms, Minors, and Minimal Obstructions to Convexity of Neural Codes

    We study open and closed convex codes from a geometric and combinatorial point of view. We prove constructive geometric results that establish new upper bounds on the open and closed embedding dimensions of intersection complete codes. We introduce a combinatorial framework of morphisms and minors …

    washington Repository record for Morphisms, Minors, and Minimal Obstructions to Convexity of Neural Codes (opens in a new tab)

  19. On two models of random graphs /

    … enumeration and properties of graphs from minor-closed classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are …

    vilnius Repository record for On two models of random graphs / (opens in a new tab)

  20. Selected Problems on Matroid Minors

    … topics include duality, connectivity, matroid minors, and Cunningham and Edmonds's tree decomposition for connected matroids. One of the most well-known excluded-minor results in matroid theory is Tutte's characterization of binary matroids. The class of binary matroids is one of the most …

    lsu-thes Repository record for Selected Problems on Matroid Minors (opens in a new tab)

Page 1 of 2