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 -