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 59 for “"induced subgraphs"”.
-
On coloring digraphs with forbidden induced subgraphs
… The field of $\chi$-boundedness studies the induced subgraphs that need to be present in a graph with high chromatic number. In this thesis, we study the equivalent of $\chi$-boundedness but with dichromatic number instead. In particular, we study the induced subgraphs of digraphs with high …
-
Foreshadowing the Grid Theorem for Induced Subgraphs
… toward a complete description of the unavoidable induced subgraphs of graphs with large treewidth. This is motivated by the Grid Theorem of Robertson and Seymour (1986) which achieves the same goal for minors (and subgraphs). Given a graph class C, we say that C is clean if the only induced …
-
Spanning and induced subgraphs in graphs and digraphs
… in relation to finding large spanning subgraphs, and removing induced subgraphs. First, we prove a generalisation of a result of Komlós, Sárközy and Szemerédi and show that for \(n\) sufficiently large, any \(n\)-vertex digraph with minimum semidegree at least \(n/2 + o(n)\) contains a …
-
On Induced Subgraphs, Degree Sequences, and Graph Structure
Finally, we define the A4-structure H of a graph G to be the 4-uniform hypergraph on the vertex set of G where four vertices comprise an edge in H if and only if they form the vertex set of an alternating 4-cycle in G. Our definition is a variation of the notion of the P4-structure, a hypergraph …
-
Forbidden substructures: induced subgraphs, Ramsey games, and sparse hypergraphs
… extremal combinatorics with respect to forbidden induced subgraphs, forbidden colored subgraphs, and forbidden subgraphs. In Chapter 2, we determine exactly which graphs H have the property that almost every H-free graph has a vertex partition into k cliques and independent sets and provide a …
-
A Linear Delay Algorithm for Enumerating All Connected Induced Subgraphs
… algorithm for enumerating all connected induced subgraphs of an undirected graph. Building on this enumeration approach, we propose an algorithm for mining maximal cohesive subgraphs that integrates vertices' attributes with subgraph enumeration. To efficiently mine all maximal cohesive …
-
Combinatorial Generalizations of Sieve Methods and Characterizing Hamiltonicity via Induced Subgraphs
… aims to characterize Hamiltonicity by means of induced subgraphs. The results in this chapter are based on the paper "Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs." Discrete Mathematics, 345(7):112869, 2022, co-authored with Joseph Cheriyan, Sepehr Hajebi, and …
-
Cubes, grids and induced subgraphs: topics in extremal and probabilistic combinatorics
<p>We begin by studying random subgraphs with a certain type of local dependence: a bond percolation model on a graph <em>G</em> is said to be 1-independent if for all vertex-disjoint sets of edges <em>S</em><sub>1</sub> and <em>S</em><sub>2</sub>, the states of the edges in <em>S</em><sub>1</sub> …
-
Induced Binary Submatroids
The notion of induced subgraphs is extensively studied in graph theory. An example is the famous Gy\'{a}rf\'{a}s-Sumner conjecture, which asserts that given a tree $T$ and a clique $K$, there exists a constant $c$ such that the graphs that omit both $T$ and $K$ as induced subgraphs have chromatic …
-
Efficient Mining of Active Components in a Network of Time Series
… (inactive). Then, at each time step, a set of induced subgraphs can be formed from the subset of active nodes; we call these induced subgraphs active components. In this research, our goal is to efficiently detect and maintain/report the active components over time.
-
Continuous Ramsey theory in higher dimensions
… the graph G-max and continuous colorings on the induced subgraphs of G-max. We give a complete categorization of the possible colorings of closed induced subgraphs in terms of basic Partitions.
-
Unavoidable Structures in Large and Infinite Graphs
… large 2-connected graphs. For the relation of induced subgraphs, Ramsey proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either Kr or Kr. It is well known that, for every positive integer r, every sufficiently large connected graph …
-
Topology, Geometry, and Combinatorics of Fine Curve Graphs
… (or lack thereof), contractibility of induced flag complexes, automorphism groups, and admissible induced subgraphs.
-
On Structures of Large Rooted Graphs
… states that K_n and ¯(K_n ) are unavoidable induced subgraphs in every sufficiently large graph. It is also motivated by a classical result of Oporowski, Oxley, and Thomas, which determines unavoidable large 3-connected minors. We first determine unavoidable induced subgraphs, and unavoidable …
-
Minimal Classes of Unbounded Clique-Width
… graph classes, those classes closed under taking induced subgraphs. A number of <i>minimal hereditary graph classes of unbounded clique-width</i> (abbreviated to <i>minimal classes</i>) have recently been identified; that is, classes containing graphs with arbitrarily large clique-width but where …
-
Topological Fingerprints in Complex Networks: From Pathway Scoring to Heuristics for Longest Simple Paths
… data, and then treating biological pathways as induced subgraphs within a larger coexpression network. From here, we want vectorized representations of these subgraphs that capture the relevant structural information, so we propose our novel graph embedding scheme, GraphOdyssey. We proceed with …
-
On the class of graphs ZP
… equality constraints hold for both G and all induced subgraphs of G, what class of graphs might arise and what is special about said graphs? Thus, we study the class ZP in which the zero forcing number and the path cover number are equal over all induced subgraphs. As many graphs are known to …
-
Independent set problems and odd-hole-preserving graph reductions
… for the exact solution of the MWIS problem on induced subgraphs of the original graph. The focus of our contribution is the use of chordal graphs as the induced subgraphs in this solution framework. Three combinatorial branch-and-bound solvers for the MWIS problem are described. All use …
-
Induced Saturation Number
<p>In this paper, we discuss the induced saturation number. It is a nice generalization of the saturation number that will allow us to consider induced subgraphs. We define the induced saturation number of a graph H to be the fewest number of gray edges in a trigraph T such that H does not appear …
-
Algebraic Methods for Reducibility in Nowhere-Zero Flows
… proof typically consists of showing that some induced subgraphs cannot appear in a minimum counter-example to some conjecture. We derive algebraic proofs of reducibility. We define variables which in some sense count the number of nowhere-zero flows of certain type in a graph and then deduce …
Page 1 of 3