Minimum degree thresholds for bipartite graph tiling

✍ Scribed by Albert Bush; Yi Zhao

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 361 KB
• Volume: 70
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20605

✦ Synopsis

Abstract

Given a bipartite graph H and a positive integer n such that v(H) divides 2__n__, we define the minimum degree threshold for bipartite H‐tiling, δ~2~(n, H), as the smallest integer k such that every bipartite graph G with n vertices in each partition and minimum degree δ(G)≥k contains a spanning subgraph consisting of vertex‐disjoint copies of H. Zhao, Hladký‐Schacht, Czygrinow‐DeBiasio determined δ~2~(n, K~s, t~) exactly for all s⩽t and suffi‐ciently large n. In this article we determine δ~2~(n, H), up to an additive constant, for all bipartite H and sufficiently large n. Additionally, we give a corresponding minimum degree threshold to guarantee that G has an H‐tiling missing only a constant number of vertices. Our δ~2~(n, H) depends on either the chromatic number χ(H) or the critical chromatic number χ~cr~(H), while the threshold for the almost perfect tiling only depends on χ~cr~(H). These results can be viewed as bipartite analogs to the results of Kuhn and Osthus [Combinatorica 29 (2009), 65–107] and of Shokoufandeh and Zhao [Rand Struc Alg 23 (2003), 180–205]. © 2011 Wiley Periodicals, Inc. J Graph Theory