Fractional Triangle Decompositions in Graphs with Large Minimum Degree

François Dross 1, *
* Auteur correspondant
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (1), pp.36-42. 〈10.1137/15M1014310〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01336680
Contributeur : François Dross <>
Soumis le : jeudi 23 juin 2016 - 15:40:42
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

fracional.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

François Dross. Fractional Triangle Decompositions in Graphs with Large Minimum Degree. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (1), pp.36-42. 〈10.1137/15M1014310〉. 〈lirmm-01336680〉

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

132