Fractional Triangle Decompositions in Graphs with Large Minimum Degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2016

Fractional Triangle Decompositions in Graphs with Large Minimum Degree

Résumé

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 non-negative 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 graph on n vertices with minimum degree at least 0.9n has a fractional triangle decomposition. This improves a result of Garaschuk that the same conclusion holds for graphs with minimum degree at least 0.956n. Together with a recent result of Barber, Kühn, Lo and Osthus, 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.
Fichier principal
Vignette du fichier
fracional.pdf (276.53 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01336680 , version 1 (23-06-2016)

Identifiants

Citer

François Dross. Fractional Triangle Decompositions in Graphs with Large Minimum Degree. SIAM Journal on Discrete Mathematics, 2016, 30 (1), pp.36-42. ⟨10.1137/15M1014310⟩. ⟨lirmm-01336680⟩
101 Consultations
281 Téléchargements

Altmetric

Partager

More