Triangle factors of graphs without large independent sets and of weighted graphs

József Balogh, Theodore Molla, Maryam Sharifzadeh

Research output: Contribution to journalArticle

Abstract

The classical Corrádi-Hajnal theorem claims that every n-vertex graph G with δ(G)≥2n/3 contains a triangle factor, when 3|n. In this paper we present two related results that both use the absorbing technique of Rödl, Ruciński and Szemerédi. Our main result determines the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with α(G) = on(n) and δ(G) ≥(1/2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratically many edges, and δ(G) ≥(1/2 + o(1))n, then G has a Kr-factor for n sufficiently large. We also propose many related open problems whose solutions could show a relationship with Ramsey-Turán theory. Additionally, we also consider a fractional variant of the Corrádi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t є (0,1) and w : E(Kn) → [0,1]. We call a triangle t-heavy if the sum of the weights on its edges is more than 3t. We prove that if 3|n and w is such that for every vertex v the sum of w(e) over edges e incident to v is at least (1+2t/3 + o(1))n, then there are n/3 vertex disjoint heavy triangles in G.

Original languageEnglish (US)
Pages (from-to)669-693
Number of pages25
JournalRandom Structures and Algorithms
Volume49
Issue number4
DOIs
StatePublished - Dec 1 2016

Keywords

  • extremal problems
  • factorization
  • matching, partitioning, covering and packing
  • probabilistic methods

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Triangle factors of graphs without large independent sets and of weighted graphs'. Together they form a unique fingerprint.

  • Cite this