Fractional Triangle Decompositions in Graphs with Large Minimum Degree

François Dross 1, *
* Corresponding author
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.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01336680
Contributor : François Dross <>
Submitted on : Thursday, June 23, 2016 - 3:40:42 PM
Last modification on : Friday, April 19, 2019 - 11:12:03 AM

File

fracional.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

152

Files downloads

330