A Median-Type Condition for Graph Tiling

Authors: Diana Piguet, Maria Saumell
Publication year: 2019
Publication type: Článek v odborném periodiku
Periodical: European Journal of Combinatorics
Projects: Extremal graph theory and applications
Bibliographic citation: PIGUET, Diana, SAUMELL, Maria. A Median-Type Condition for Graph Tiling. European Journal of Combinatorics. 2019, 77(March), 90-101. ISSN 0195-6698. E-ISSN 1095-9971
Dostupné z: doi:10.1016/j.ejc.2018.11.004.
DOI: 10.1016/j.ejc.2018.11.004
ID: 498771
Online record: View online record

Abstract

Komlós (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.