Covering a Graph by Forests and a Matching - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2011

Covering a Graph by Forests and a Matching

Résumé

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.

Dates et versions

lirmm-01263789 , version 1 (28-01-2016)

Identifiants

Citer

Tomáš Kaiser, Mickaël Montassier, André Raspaud. Covering a Graph by Forests and a Matching. SIAM Journal on Discrete Mathematics, 2011, 25 (4), pp.1804-1811. ⟨10.1137/100818340⟩. ⟨lirmm-01263789⟩
103 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More