Covering a Graph by Forests and a Matching - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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.

Domains

Discrete Mathematics [cs.DM]

Mickael Montassier  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01263789

Submitted on : Thursday, January 28, 2016-11:34:26 AM

Last modification on : Tuesday, January 23, 2024-3:43:45 AM

Consult the full text

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER ANR
106 View
0 Download

Altmetric

Share

More