Name
Abstract | ||
|---|---|---|
The classical Corradi-Hajnal theorem claims that every n-vertex graph G with delta(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 Rodl, Rucinski and Szemeredi. 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 alpha(G) = o(n) and delta(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 delta(G) >= (1/2 + o(1)) n, then G has a K-r -factor for n sufficiently large. We also propose many related open problems whose solutions could show a relationship with Ramsey-Turan theory. Additionally, we also consider a fractional variant of the Corradi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t is an element of(0, 1) and w : E(K-n) -> [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. (C) 2016Wiley Periodicals, Inc. Random Struct. Alg., 49, 669-693, 2016 |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/rsa.20670 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
extremal problems,factorization,matching,partitioning,covering and packing,probabilistic methods | Sublinear function,Discrete mathematics,Graph,Independence number,Combinatorics,Vertex (geometry),Quadratic equation,Probabilistic method,Factorization,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
49.0 | SP4.0 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Theodore Molla | 2 | 23 | 6.23 |
| Maryam Sharifzadeh | 3 | 11 | 3.83 |