Triangle-tilings in graphs without large independent sets

Jozsef Balogh; Andrew McDowell; Theodore Molla; Richard Mycroft

doi:10.1017/S0963548318000196

Triangle-tilings in graphs without large independent sets

Jozsef Balogh, Andrew McDowell, Theodore Molla, Richard Mycroft

Mathematics

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

237 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 language	English
Number of pages	24
Journal	Combinatorics, Probability and Computing
Early online date	9 May 2018
DOIs	https://doi.org/10.1017/S0963548318000196
Publication status	E-pub ahead of print - 9 May 2018

Access to Document

10.1017/S0963548318000196Licence: None: All rights reserved

Balogh_et_al_Triangle-tilings_in_graphs_Combinatorics_Probability_and_Computing_2018
Checked for eligibility: 15/01/2018
Accepted author manuscript, 402 KBLicence: None: All rights reserved

Embeddings in hypergraphs
Mycroft, R. (Principal Investigator)
Engineering & Physical Science Research Council
30/03/15 → 29/03/17
Project: Research Councils

Cite this

@article{a4fe856c8b834be0a38b72ae095af68e,

title = "Triangle-tilings in graphs without large independent sets",

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. ",

author = "Jozsef Balogh and Andrew McDowell and Theodore Molla and Richard Mycroft",

year = "2018",

month = may,

day = "9",

doi = "10.1017/S0963548318000196",

language = "English",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Triangle-tilings in graphs without large independent sets

AU - Balogh, Jozsef

AU - McDowell, Andrew

AU - Molla, Theodore

AU - Mycroft, Richard

PY - 2018/5/9

Y1 - 2018/5/9

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.

U2 - 10.1017/S0963548318000196

DO - 10.1017/S0963548318000196

M3 - Article

SN - 0963-5483

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

ER -

Triangle-tilings in graphs without large independent sets

Abstract

Access to Document

Fingerprint

Projects

Embeddings in hypergraphs

Cite this