Triangle-tilings in graphs without large independent sets

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • Department of Mathematics, University of Illinois at Urbana-Champaign
  • University of South Florida

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.

Details

Original languageEnglish
Number of pages24
JournalCombinatorics, Probability and Computing
Early online date9 May 2018
Publication statusE-pub ahead of print - 9 May 2018