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 11 of 11 for “"odd cycle"”.
-
On matchings and factors of graphs /
… existence of a (g, f)-factor in graphs with the odd-cycle property, which is simpler than that of Lovasz's (g, f)-Factor Theorem. From this, we derive some further results, and we show that (a) every r-regular graph G with the odd-cycle property has a k-factor, where 0 ≤ k ≤ r and k|V(G)| ≡ 0 …
-
Variants of zero forcing and their applications to the minimum rank problem
… described by the graph. In Chapter 2, the odd cycle zero forcing number Zoc(G) and the enhanced odd cycle zero forcing number Ẑoc(G) are introduced as bounds for the maximum nullities of loop graphs G and simple graphs G, respectively. Also, a relation between loop graphs and simple graphs …
-
Density and Structure of Homomorphism-Critical Graphs
… Jaeger made the following conjecture concerning odd-cycle critical graphs: every planar graph of girth at least $4t$ admits a homomorphism to $C_{2t+1}$ (or equivalently, has a $\tfrac{2t+1}{t}$-circular colouring). The best known result for the $t=3$ case states that every planar graph of girth …
-
Detecting graphs with induced cycles in limited-bandwidth communication networks
… show that, if P is a graph containing an induced cycle of length at least 4, then detecting a rainbow copy of P (in terms of vertex colourings or edge colourings) takes at least Ω(n/ log n) in the CONGEST model. Motivated by this result, we go on to show that, if P is a necklace graph containing …
-
Upper density problems in infinite Ramsey theory
… forests, bipartite factors, clique factors and odd cycle factors. We also determine the value of the Ramsey density of all locally finite graphs, up to a factor of 2. We also study a list coloring variant of the same problem. We show that there exists a way of assigning a list of size two to …
-
How to Color Graphs, and How Not to Chase Pointers
… be Δ-colored as long as it is not a clique or an odd-cycle. We show a 1-pass, O(n polylog(n)) space algorithm that can Δ-color a graph given as a stream. This is optimal up to log n factors. In the number-in-hand communication model, the input to some relation is partitioned between k players, who …
-
Tree Spanners of Simple Graphs
… of a graph. Although graphs in U(2) do not have cycles of length greater than 4, graphs in U(3) may contain cycles of arbitrary length. It turns out that any even cycle is an induced subgraph of a graph in U(3), while no graph in U(3) contains an induced odd cycle other than a triangle; graphs in …
-
Putting the pieces together: from graph decompositions to Ramsey theory
… with at most $2 \cdot n / (d+1)$ paths and a cycle-factor with at most $\mathcal{O}((n \log d) / d)$ cycles. This confirms a conjecture of Feige and Fuchs, resolves a conjecture of Magnant and Martin up to a factor of two, and yields an efficient algorithm for finding short tours in connected …
-
On Induced Saturation in Graphs and Tournaments
… H-induced-saturated graphs exist for every even cycle H. This is particularly intriguing because, in contrast, Behrens et al. [1] gave a short proof that H-induced-saturated graphs exist when H is an odd cycle (except for the triangle, which is complete). A “halfway” result toward settling the …
-
Directed Graphs: Fixed-Parameter Tractability & Beyond
… Cut, Multicut, Subset Feedback Vertex Set, Odd Cycle Transversal, etc. was open. In the first part of the thesis, we develop the framework of <italic>shadowless solutions</italic> for a general class of transversal problems in directed graphs. For this class of problems, we reduce the …
-
On Reconfiguration Problems: Structure and Tractability
… Cover, Independent Set, Feedback Vertex Set, and Odd Cycle Transversal, and provide lower bounds, polynomial-time algorithms, and fixed-parameter tractable algorithms. In doing so, we answer some of the questions left open in recent work and push the known boundaries between tractable and …