Decomposing a graph into forests

作者：Montassier Mickael^*; de Mendez Patrice Ossona; Raspaud Andre; Zhu Xuding

来源：Journal of Combinatorial Theory - Series B, 2012, 102(1): 38-52.

DOI：10.1016/j.jctb.2011.04.001

• Fractional arboricity
• Maximum average degree
• Forests
• Decomposition
• Matching
• Planar graph
• Girth

The fractional arboricity gamma(f) (C) of a graph G is the maximum of the ratio vertical bar E(G[X])vertical bar/(vertical bar X vertical bar - 1) over all the induced subgraphs G[X] of G. In this paper, we propose a conjecture which says that every graph G with gamma(f)(G) <= k + d/k+d+1 decomposes into k + 1 forests, and one of the forests has maximum degree at most d. We prove two special cases of this conjecture: if G is a graph with fractional arboricity at most 4, then G decomposes into a forest and a matching. If G is a graph with fractional arboricity at most 3/2, then G decomposes into a forest and a linear forest. In particular, every planar graph of girth at least 8 decomposes into a forest and a matching, and every planar graph of girth at least 6 decomposes into a forest and a linear forest. This improves earlier results concerning decomposition of planar graphs, and the girth condition is sharp, as there are planar graphs of girth 7 which do not decompose into a forest and a matching, and there are planar graphs of girth 5 which do not decompose into a forest and a linear forest. The bound in the conjecture above is sharp: We shall show that for any epsilon > 0, there is a graph G with gamma(f) (C) < k + d/k+d+1, + epsilon, and yet G cannot be decomposed into k forests plus a graph of maximum degree at most d. On the other hand, we show that for any positive integer k and real number 0 <

• 出版日期2012-1
• 单位浙江师范大学