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"”.
-
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 …
-
Splittability within minor-closed classes to graphs of low maximum degree
Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K$_5$ ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K$_5$ ως έλασσον μέγιστου βαθμού 22, και ρώτησε αν αυτός είναι …
-
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 …
-
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 …
-
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, …
-
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 …
-
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 …
-
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 …
-
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, …
-
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 …
-
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 …
-
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 …
-
Local properties of graphs with large chromatic number
… a conjecture of Geelen that every proper vertex-minor-closed class of graphs is $\chi$-bounded.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
Page 1 of 2