A Median-Type Condition for Graph Tiling

0498771 - ÚI 2020 RIV GB eng J - Journal Article
Piguet, Diana - Saumell, Maria
A Median-Type Condition for Graph Tiling.
European Journal of Combinatorics. Roč. 77, March (2019), s. 90-101. ISSN 0195-6698. E-ISSN 1095-9971
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : graph tilling * LP duality * regularity method * median-type degree condition
OECD category: Pure mathematics
Impact factor: 0.848, year: 2019
Method of publishing: Limited access
http://dx.doi.org/10.1016/j.ejc.2018.11.004

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.
Permanent Link: http://hdl.handle.net/11104/0291037