# 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 language English (US) 669-693 25 Random Structures and Algorithms 49 4 https://doi.org/10.1002/rsa.20670 Published - 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