Triangle-Tilings in Graphs Without Large Independent Sets

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

doi:10.1017/S0963548318000196

Triangle-Tilings in Graphs Without Large Independent Sets

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

Mathematics

Research output: Contribution to journal › Article › peer-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 K_r-free and n is divisible by 3.

Original language	English (US)
Pages (from-to)	449-474
Number of pages	26
Journal	Combinatorics Probability and Computing
Volume	27
Issue number	4
DOIs	https://doi.org/10.1017/S0963548318000196
State	Published - Jul 1 2018

ASJC Scopus subject areas

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

Online availability

10.1017/S0963548318000196

Library availability

Discover UIUC Full Text

Cite this

@article{86d96036777a42109513c3d3bf25c20d,

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 = "J{\'o}zsef Balogh and Andrew McDowell and Theodore Molla and Richard Mycroft",

note = "† 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.",

year = "2018",

month = jul,

day = "1",

doi = "10.1017/S0963548318000196",

language = "English (US)",

volume = "27",

pages = "449--474",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "4",

}

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 - † 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.

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 - https://www.scopus.com/pages/publications/85047148710

UR - https://www.scopus.com/pages/publications/85047148710#tab=citedBy

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 -

Triangle-Tilings in Graphs Without Large Independent Sets

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this