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 16 of 16 for “"Graphs on surfaces"”.
-
Color-critical graphs on surfaces
… this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general …
-
Acyclic Colouring of Graphs on Surfaces
… cycles. In 1979, Borodin proved that planar graphs are acyclically 5-colourable, an analog of the Four Colour Theorem. Kawarabayashi and Mohar proved in 2010 that "locally" planar graphs are acyclically 7-colourable, an analog of Thomassen's result that "locally" planar graphs are …
-
5-list-coloring graphs on surfaces
Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general …
-
Tightening curves and graphs on surfaces
Any continuous deformation of closed curves on a surface can be decomposed into a finite sequence of local changes on the structure of the curves; we refer to such local operations as homotopy moves. Tightening is the process of deforming given curves into their minimum position; that is, those …
-
Highly symmetric embeddings of graphs on surfaces
This thesis considers highly symmetric maps, that is embeddings of graphs in surfaces such that the automorphism group is “large”. This may be when the automorphism group of the map acts regularly on the flag-set of the map, as for the fully regular maps studied in Part I. In contrast, Part II …
-
Two Results in Drawing Graphs on Surfaces
In this work we present results on crossing-critical graphs drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We first give an infinite family of graphs that are 2-crossing-critical on the projective plane. Using this result, we construct …
-
Defect-1 Choosability of Graphs on Surfaces
… graph is called chromatic number of that graph. One generalization of this classical problem is to relax the requirement that the maximum degree of the graph induced by the vertices coloured the same colour be zero, and instead allow it to be some integer d. For d = 0, we are back at the …
-
Edge colorings of graphs on surfaces and star edge colorings of sparse graphs
In my dissertation, I present results on two types of edge coloring problems for graphs. For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. …
-
Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem
… this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low …
-
Reducible and toroidal Dehn filling with distance 3
This dissertation is an investigation into the classification of all hyperbolic manifolds which admit a reducible Dehn filling and a toroidal Dehn filling with distance 3. The first example was given by Boyer and Zhang. They used the Whitehead link. Eudave-Muñoz and Wu gave an infinite family of …
-
Embedded graph 3-coloring and flows in orientable surfaces
… an algorithm for 3-coloring near-quadrangulations of the torus with bounded edgewidth and for deciding 3-colorability of triangle-free toroidal graphs. We generalize this by leveraging the duality between flows and colorings to design an efficient algorithm for the extension of a 3-precoloring …
-
Isometric and topological folding of manifolds
… of isometric foldings studies the stratification determined by the folds or singularities, and relates this structure to classical ideas of Hopf degree, volume and covering spaces. </p><p>The idea of topological folding is modelled on that of isometric folding, but in the absence of metrical …
-
Real Second-Order Freeness and Fluctuations of Random Matrices
We introduce real second-order freeness in second-order noncommutative probability spaces. We demonstrate that under this definition, independent ensembles of the three real models of random matrices which we consider, namely real Ginibre matrices, Gaussian orthogonal matrices, and real Wishart …
-
Cayley maps for certain cyclic groups with odd generators
For this thesis I plan on using the AMS format. My Thesis Advisor and I will meet regularly to discuss my thesis topic, prove conjectures, write results as we make progress, develop a program for calculation of genus values under certain constraints, and then organize the work for both oral and …
-
Unambiguous logarithmic space bounded computations
… complexity investigates the power and limitations of a computational model (e.g. a Turing machine) which has a limited amount of workspace to perform its computation. Particularly interesting is the case when the space is only logarithmic in the input size. Unambiguous computation is a natural …