Abstract
We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an n-vertex graph G with sublinear independence number. In this setting, we show that if δ(G) ≥ n/3 + o(n), then G has a triangle-tiling covering all but at most four vertices. Also, for every r ≥ 5, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that G is Kr-free and n is divisible by 3.
Original language | English (US) |
---|---|
Pages (from-to) | 449-474 |
Number of pages | 26 |
Journal | Combinatorics Probability and Computing |
Volume | 27 |
Issue number | 4 |
DOIs | |
State | Published - Jul 1 2018 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics