Tiling in bipartite graphs with asymmetric minimum degrees

The problem of determining the optimal minimum degree condition for a balanced bipartite graph on 2ms vertices to contain m vertex disjoint copies of Ks,s was solved by Zhao [10]. Later Hladky ́ and Schacht [5], and Czygrinow and DeBiasio [1] determined the optimal minimum degree condition for a balanced bipartite graph on 2m(s + t) vertices to contain m vertex disjoint copies of Ks,t for fixed positive integers s < t. For a balanced bipartite graph G[U, V], let δU = min{deg(u) : u ∈ U} and δV = min{deg(v): v ∈ V}. We consider the problem of determining the optimal value of δU + δV which guarantees that G can be tiled with Ks,s. We show that the optimal value depends on D: = |δV − δU |. When D is small, we show that δU + δV ≥ n+ 3s − 5 is best possible. As D becomes larger, we show that δU + δV can be made smaller, but no smaller than n+ 2s − 2 d se. However, when D = n−C for some constant C, we show that there exist graphs with δU +δV ≥ n+ss1/3 which cannot be tiled with Ks,s.