Fractional triangle decompositions in graphs with large minimum degree. (English) Zbl 1329.05244
Summary: A triangle decomposition of a graph is a partition of its edges into triangles. A fractional triangle decomposition of a graph is an assignment of a nonnegative weight to each of its triangles such that the sum of the weights of the triangles containing any given edge is one. We prove that every graph on \(n\) vertices with minimum degree at least \(0.9n\) has a fractional triangle decomposition. This improves a result of K. Garaschuk [Linear methods for rational triangle decompositions. Victoria, BC: University of Victoria (PhD Thesis) (2014)] that the same conclusion holds for graphs with minimum degree at least \(0.956n\). Together with a recent result of B. Barber et al. [Adv. Math. 288, 337–385 (2016; Zbl 1328.05145)], this implies that for all \(\epsilon > 0\), every large enough triangle divisible graph on \(n\) vertices with minimum degree at least \((0.9 + \epsilon)n\) admits a triangle decomposition.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C07 | Vertex degrees |
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 1328.05145References:
| [1] | B. Barber, D. Kühn, A. Lo, R. Montgomery, and D. Osthus, {\it Fractional Clique Decompositions of Dense Graphs and Hypergraphs}, preprint, arXiv:1507.04985, 2015. · Zbl 1371.05226 |
| [2] | B. Barber, D. Kühn, A. Lo, and D. Osthus, {\it Edge-Decompositions of Graphs with High Minimum Degree}, preprint, arXiv:1410.5750, 2014. · Zbl 1346.05224 |
| [3] | P. Dukes, {\it Rational decomposition of dense hypergraphs and some related eigenvalue estimates}, Linear Algebra Appl., 436 (2012), pp. 3736-3746. · Zbl 1241.05113 |
| [4] | P. Dukes, {\it Corrigendum to “Rational decomposition of dense hypergraphs and some related eigenvalue estimates},” Linear Algebra Appl., 467 (2015), pp. 267-269. · Zbl 1303.05151 |
| [5] | K. Garaschuk, {\it Linear Methods for Rational Triangle Decompositions}, Ph.D. thesis, University of Victoria, 2014. |
| [6] | T. Gustavsson, {\it Decompositions of Large Graphs and Digraphs with High Minimum Degree}, Ph.D. thesis, University of Stockholm, 1991. |
| [7] | P. Keevash, {\it The Existence of Designs}, preprint, arXiv:1401.3665, 2014. |
| [8] | T. P. Kirkman, {\it On a problem in combinatorics}, Cambridge Dublin Math. J., 2 (1847), pp. 191-204. |
| [9] | C. S. J. Nash-Williams, {\it An unsolved problem concerning decomposition of graphs into triangles}, in Combinatorial Theory and Its Applications III, North-Holland, Amsterdam, 1970, pp. 1179-1183. |
| [10] | R. M. Wilson, {\it Decomposition of complete graphs into subgraphs isomorphic to a given graph}, Congr. Numer., 15 1975, pp. 647-659. · Zbl 0322.05116 |
| [11] | R. Yuster, {\it The decomposition threshold for bipartite graphs with minimum degree one}, Random Structures Algorithms, 21 (2002), pp. 121-134. · Zbl 1018.05090 |
| [12] | R. Yuster, {\it Asymptotically optimal \(K_k\)-packings of dense graphs via fractional \(K_k\)-decompositions}, J. Combin. Theory Ser. B, 95 (2005), pp. 1-11. · Zbl 1070.05071 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
