A median-type condition for graph tiling

摘要

Komlos (2000) determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree. (C) 2018 Elsevier Ltd. All rights reserved.