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"”.

  1. 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 …

    gatech Repository record for Color-critical graphs on surfaces (opens in a new tab)

  2. 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 …

    waterloo Repository record for Acyclic Colouring of Graphs on Surfaces (opens in a new tab)

  3. 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 …

    gatech Repository record for 5-list-coloring graphs on surfaces (opens in a new tab)

  4. 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 …

    uiuc Repository record for Tightening curves and graphs on surfaces (opens in a new tab)

  5. 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 …

    the-open-u Download PDF for Highly symmetric embeddings of graphs on surfaces (opens in a new tab)

  6. 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 …

    lsu-thes Repository record for Two Results in Drawing Graphs on Surfaces (opens in a new tab)

  7. 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 …

    ottawa-retro Repository record for Defect-1 Choosability of Graphs on Surfaces (opens in a new tab)

  8. 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. …

    wvu Repository record for Edge colorings of graphs on surfaces and star edge colorings of sparse graphs (opens in a new tab)

  9. 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 …

    gatech Repository record for Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem (opens in a new tab)

  10. 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 …

    texas Repository record for Reducible and toroidal Dehn filling with distance 3 (opens in a new tab)

  11. 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 …

    iastate Repository record for Embedded graph 3-coloring and flows in orientable surfaces (opens in a new tab)

  12. 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 …

    soton Download PDF for Isometric and topological folding of manifolds (opens in a new tab)

  13. 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 …

    queens Repository record for Real Second-Order Freeness and Fluctuations of Random Matrices (opens in a new tab)

  14. 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 …

    unlv Repository record for Cayley maps for certain cyclic groups with odd generators (opens in a new tab) Download PDF for Cayley maps for certain cyclic groups with odd generators (opens in a new tab)

  15. 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 …

    nebraska Repository record for Unambiguous logarithmic space bounded computations (opens in a new tab)