Covering a Graph by Forests and a Matching

Abstract : We prove that for any positive integer k, the edges of any graph whose fractional arboricity is at most $k + 1/(3k+2)$ can be decomposed into k forests and a matching. This is a partial result in the direction of the “Nine Dragon Tree” conjecture of Montassier et al.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (4), pp.1804-1811. 〈10.1137/100818340〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01263789
Contributeur : Mickael Montassier <>
Soumis le : jeudi 28 janvier 2016 - 11:34:26
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Citation

Tomáš Kaiser, Mickaël Montassier, André Raspaud. Covering a Graph by Forests and a Matching. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (4), pp.1804-1811. 〈10.1137/100818340〉. 〈lirmm-01263789〉

Partager

Métriques

Consultations de la notice

70