A Median-Type Condition for Graph Tiling

Authors: Diana Piguet, Maria Saumell
Publication year: 2017
Publication type: Článek v odborném periodiku
Periodical: Electronic Notes in Discrete Mathematics
Projects: Extremal graph theory and applications
Bibliographic citation: PIGUET, Diana, SAUMELL, Maria. A Median-Type Condition for Graph Tiling. Electronic Notes in Discrete Mathematics. 2017, 61(August), 979-985. ISSN 1571-0653
Dostupné z: doi:10.1016/j.endm.2017.07.062
DOI: 10.1016/j.endm.2017.07.062
ID: 477018

Abstract

Komlós [Komlós: Tiling Turán Theorems, Combinatorica, 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 H. 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.