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 12 of 12 for “"induced subgraph"”.
-
Bounding the Number of Graphs Containing Very Long Induced Paths
Induced graphs are used to describe the structure of a graph, one such type of induced graph that has been studied are long paths. <p>In this thesis we show a way to represent such graphs in terms of an array with two colors and a labeled graph. Using this representation and the techniques of Polya …
-
Forbidden Substructures in Graphs and Trigraphs, and Related Coloring Problems
… G). A graph G is perfect provided that for every induced subgraph H of G, χ(H) = ω(H). This thesis addresses several problems from the theory of perfect graphs and generalizations of perfect graphs. The bull is a five-vertex graph consisting of a triangle and two vertex-disjoint pendant edges; a …
-
A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes
… paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such …
-
Universal Hypergraphs.
… of a smaller size <em>k</em> < <em>n</em> as an induced subgraph. A <em>hypergraph</em> is a discrete structure on <em>n</em> vertices in which edges can be of any size, unlike graphs, where the edge size is always two. If all edges are of size three, then the hypergraph is said to be 3-uniform. …
-
Better-Quasi-Orders: Extensions and Abstractions
… of graphs are better-quasi-ordered under the induced subgraph relation, thus generalising results of Damaschke and Thomass�e. We investigate abstract better-quasi-orders by modifying the normal de�nition of better-quasi-order to use an alternative Ramsey space rather than exclusively the …
-
Extremal and Structural Problems of Graphs
… each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct …
-
On some problems in reconstruction
… it is determined by its {\it deck} of unlabeled subgraphs obtained by deleting one vertex; a {\it card} is one of these subgraphs. The {\it Reconstruction Conjecture} asserts that all graphs with at least three vertices are reconstructible. In Chapter $2$ we consider $k$-deck reconstruction of …
-
Results in Ramsey theory and extremal graph theory
… hypercube graph $Q_n$. Huang showed that every induced subgraph of the hypercube with $2^{n-1}+1$ vertices has maximum degree at least $\lceil\sqrt{n}\rceil$, which resolved a major open problem in computer science known as the Sensitivity Conjecture. Huang asked whether analogous results could …
-
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 …
-
Tournaments With Forbidden Substructures and the Erdos-Hajnal Conjecture
… on n vertices that does not contain H as an induced subgraph contains a clique or a stable set of size at least n^{ɛ(H)}. In 2001 Alon, Pach and Solymosi proved that the conjecture has an equivalent directed version, where undirected graphs are replaced by tournaments and cliques and stable …
-
Results in Extremal Graph Theory, Ramsey Theory and Additive Combinatorics
… properly edge-coloured graph without a rainbow subgraph isomorphic to H. We prove that ex*(n,C_{2k})=O(n^{1+1/k}), which is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstraete. We use the same method to answer several further questions in various topics: among others, a …
-
Proper connection number of graphs
… in the terms of connectivity and forbidden induced subgraphs $S_{i,j,k}$, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where $S_{i,j,k}$ is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common). Recently, there are not so many results on …