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 3 of 3 for “"1-planar graph"”.
-
Bounds on Maximum Matchings in 1-Planar Graphs
… we study lower bounds on maximum matchings in 1-planar graphs. We expand upon the tools used for proofs of matching bounds in other classes of graphs as well as some original ideas in order to find these bounds. The first novel results we provide are lower bounds on maximum matchings in 1-planar …
-
List Coloring Some Classes of 1-Planar Graphs
In list coloring we are given a graph G and a list assignment for G which assigns to each vertex of G a list of possible colors. We wish to find a coloring of the vertices of G such that each vertex uses a color from its list and adjacent vertices are given different colors. In this thesis we study …
-
Testing vertex connectivity of bowtie 1-plane graphs
A separating set of a connected graph $G$ is a set of vertices $S$ such that $G-S$ is disconnected. $S$ is a minimum separating set of $G$ if there is no separating set of $G$ with fewer vertices than $S$. The size of a minimum separating set of $G$ is called the vertex connectivity of $G$. A …