Erdos proved the well-known result that every graph has a spanning, bipartite subgraph such that every vertex has degree at least half of its original degree. Bollobas and Scott conjectured that one can get a slightly weaker result if we require the subgraph to be not only spanning and bipartite, but also balanced. We prove this conjecture for graphs of maximum degree 3.
The majority of the paper however, will focus on graph tiling. Graph tiling (or sometimes referred to as graph packing) is where, given a graph H, we find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove an asymptotic minimum degree condition for an arbitrary bipartite graph G to be tiled by another arbitrary bipartite graph H. This proves a conjecture of Zhao and also implies an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.
| Identifer | oai:union.ndltd.org:GEORGIA/oai:digitalarchive.gsu.edu:math_theses-1071 |
| Date | 13 July 2009 |
| Creators | Bush, Albert |
| Publisher | Digital Archive @ GSU |
| Source Sets | Georgia State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Mathematics Theses |
Page generated in 0.0023 seconds