Back to Search
Start Over
Triangle factors of graphs without large independent sets and of weighted graphs
- Source :
- Random Structures & Algorithms. 49:669-693
- Publication Year :
- 2016
- Publisher :
- Wiley, 2016.
-
Abstract
- The classical Corr adi-Hajnal theorem claims that every n-vertex graph G with (G) 2n=3 contains a triangle factor, when 3jn. In this paper we asymptotically determine 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) = o(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 quadratic many edges, and (G) (1=2 +o(1))n, then G has a Kr-factor for n suciently large. We also propose many related open problems whose solutions could show a relationship with RamseyTur an theory. Additionally, we also consider a fractional variant of the Corr adi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t2 (0; 1) and w : E(Kn)! [0; 1]. We call a triangle in Kn heavy if the sum of the weights on its edges is more than 3t. We prove that if 3jn and w is such that for every vertex v the sum of w(e)
- Subjects :
- Vertex (graph theory)
Discrete mathematics
Conjecture
Sublinear function
Applied Mathematics
General Mathematics
010102 general mathematics
0102 computer and information sciences
01 natural sciences
Computer Graphics and Computer-Aided Design
Graph
Combinatorics
Quadratic equation
Probabilistic method
Factorization
010201 computation theory & mathematics
0101 mathematics
Software
Independence number
Mathematics
Subjects
Details
- ISSN :
- 10982418 and 10429832
- Volume :
- 49
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi...........1885a33a910334036292e6df463e7e85