Covering a Graph by Forests and a Matching - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles SIAM Journal on Discrete Mathematics Year : 2011

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.

Dates and versions

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

Identifiers

Cite

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 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More