Triangle-tilings in graphs without large independent sets

Jozsef Balogh, Andrew McDowell, Theodore Molla, Richard Mycroft

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
157 Downloads (Pure)

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
Number of pages24
JournalCombinatorics, Probability and Computing
Early online date9 May 2018
DOIs
Publication statusE-pub ahead of print - 9 May 2018

Fingerprint

Dive into the research topics of 'Triangle-tilings in graphs without large independent sets'. Together they form a unique fingerprint.

Cite this