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 18 of 18 for “"triangle-free graphs"”.
-
When are random regular triangle-free graphs bipartite?
Let $\mathcal T_{n,m}$ denote the set of triangle-free graphs on $n$ vertices with $m$ edges where $m = m(n)$. A natural and well-studied question in random graph theory is ``for large $n$, how large is $\mathcal T_{n,m}$?" This question has been answered when $m \le n^{3/2-\eps}$ for some …
-
Extremal problems on counting combinatorial structures
… has $\floor{n^2/4}$ edges. Since all of its subgraphs are triangle-free, the number of (labeled) triangle-free graphs on $n$ vertices is at least $2^{\floor{n^2/4}}$. This was shown to be the correct order of magnitude in a celebrated paper Erd\H{o}s, Kleitman, and Rothschild from 1976, where …
-
Maximum number of cycles in graphs and multigraphs
… number of cycles for the following classes of graphs is considered: triangle-free graphs; K_r-free graphs; graphs with m edges; graphs with n vertices and m edges; multigraphs with m edges and multigraphs with n vertices and m edges.
-
Chromatic Thresholds of Regular Graphs with Small Cliques
<p>The chromatic threshold of a class of graphs is the value <em>θ</em> such that any graph in this class with a minimum degree greater than <em>θn</em> has a bounded chromatic number. Several important results related to the chromatic threshold of triangle-free graphs have been reached in the last …
-
Applications of flag algebras to problems in extremal graph theory
… use flag algebras to identify large bipartite subgraphs of triangle-free graphs.
-
Colouring Cayley Graphs
… about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three. 2. We will prove a general statement that all vertex-transitive maximal triangle-free graphs on <i>n</i> vertices with valency greater …
-
The computational complexity of edge colouring restricted graphs
… complexity of edge colouring restricted graphs. Previous work has established that the chromatic index problem restricted to k-regular graphs for any fixed k-3 remains NP-complete, whereas the problem restricted to bipartite graphs and partial k-trees for fixed k is in P. We show that …
-
Embedded graph 3-coloring and flows in orientable surfaces
… 3-colorable, Grötzsch showed that every planar triangle-free graph is 3-colorable. This motivated further study of the 3-colorabliity of certain graph classes. Dvořák and Pekárek created an algorithm for 3-coloring near-quadrangulations of the torus with bounded edgewidth and for deciding …
-
An introduction to the theory of random graphs
… such as Mycielski's construction of a family of triangle-free graphs with high chromatic number and results in Ramsey theory. Next we introduce the concept of a random graph and present two of the most famous proofs in graph theory using the theory random graphs. These include the proof of the …
-
Homomorphisms of Graphs
Understanding the structure of graphs is fundamental to advances in many areas of graph theory, as well as in many applications. In many cases, an analysis of the structure of graphs follows one of two approaches; either many structural properties are considered over a restricted class of graphs, …
-
Forbidden subgraphs and 3-colorability
… is a well-known NP-complete problem, even for triangle-free graphs. Intuitively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic …
-
Algorithmic approaches to problems in probabilistic combinatorics
… 1. We study the structural properties of the triangle-free graphs generated by a semi-random variant of triangle-free process and obtain a packing extension of Kim's famous R(3,t) results. This allows us to resolve a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabo, …
-
Combinatorial Generalizations of Sieve Methods and Characterizing Hamiltonicity via Induced Subgraphs
… the combinatorial Turán sieve to count labelled graphs and we apply the combinatorial Selberg sieve to count subspaces of finite spaces. Finding sufficient conditions for Hamiltonicity in graphs is a classical topic, where the difficulty is bracketed by the NP-hardness of the associated decision …
-
Solving Hard Graph Problems with Combinatorial Computing and Optimization
… defined as the smallest order of a $K_4$-free graph that is not the union of two triangle-free graphs. A notoriously difficult problem associated with Ramsey theory, the best known bounds on it prior to this work were $19 leq F_e(3,3;4) leq 941$. We improve the upper bound to $F_e(3,3;4) …
-
Recoloring in Hereditary Graph Classes: Structure and Decomposition
… have been made to study the recolorability of graphs defined by forbidden induced subgraphs. We prove that, for a fixed graph H, every H-free graph is recolorable if and only if H is an induced subgraph of P4 or P3+P1. We also start an investigation into this problem for classes of graphs …
-
On Asymmetric Induced Saturation
Given a graph H, a graph G is H-free if no induced subgraph of G is isomorphic to H. A graph G is H-induced-saturated if G is H-free but deleting or adding any edge in G creates an induced copy of H. The notion of induced saturation originated in a 2012 work by Martin and Smith [23] concerning the …
-
Fractional Chromatic Numbers and Spectra of Graphs
… recent study of fractional chromatic numbers of graphs, spectra of edge-independent random graphs, Laplacian spectra of hypergraphs, and loose Laplacian spectra of random hypergraphs. For a graph $G$, let $\chi_f(G)$ be the fractional chromatic number of $G$. Based on the study of independence …
-
Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm
… that improves bounds on the density of critical graphs without large cliques, a long-standing problem, answering a question of Kostochka and Yancey. In the proof, we use a novel application of the discharging method to find a set of vertices for which any precoloring can be extended to the …