Triangle-Tilings in Graphs Without Large Independent Sets

József Balogh, Andrew McDowell, Theodore Molla, Richard Mycroft

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)449-474
Number of pages26
JournalCombinatorics Probability and Computing
Volume27
Issue number4
DOIs
StatePublished - Jul 1 2018

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Triangle-Tilings in Graphs Without Large Independent Sets'. Together they form a unique fingerprint.

Cite this