Title

Triangle-Tilings in Graphs Without Large Independent Sets

Document Type

Article

Publication Date

7-2018

Digital Object Identifier (DOI)

https://doi.org/10.1017/S0963548318000196

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.

Was this content written or created while at USF?

Yes

Citation / Publisher Attribution

Combinatorics, Probability and Computing, v. 27, issue 4, p. 449-474

Share

COinS