TY - JOUR
T1 - Triangle-Tilings in Graphs Without Large Independent Sets
AU - Balogh, József
AU - McDowell, Andrew
AU - Molla, Theodore
AU - Mycroft, Richard
N1 - Funding Information:
† Research partially supported by NSA grant H98230-15-1-0002, NSF grant DMS-1500121 and an Arnold O. Beckman Research Award (UIUC Campus Research Board 15006). ‡The work for this paper was carried out while this author was a postdoctoral researcher at the University of Birmingham. § Research partially supported by NSF Grant DMS-1500121. The work for this paper was carried out while this author was a postdoctoral researcher at the University of Illinois at Urbana-Champaign. ¶ Research partially supported by EPSRC grant EP/M011771/1. The authors are grateful to the BRIDGE strategic alliance between the University of Birmingham and the University of Illinois at Urbana-Champaign. This research was conducted as part of the Building Bridges in Mathematics BRIDGE Seed Fund project.
Publisher Copyright:
© 2018 Cambridge University Press.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85047148710&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047148710&partnerID=8YFLogxK
U2 - 10.1017/S0963548318000196
DO - 10.1017/S0963548318000196
M3 - Article
AN - SCOPUS:85047148710
SN - 0963-5483
VL - 27
SP - 449
EP - 474
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
IS - 4
ER -