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
Scholar Commons Citation
Balogh, Jozsef; McDowell, Andrew; Molla, Theodore; and Mycroft, Richard, "Triangle-Tilings in Graphs Without Large Independent Sets" (2018). Mathematics and Statistics Faculty Publications. 24.
https://digitalcommons.usf.edu/mth_facpub/24
