Originator: Douglas West (presented by Douglas West - REGS 2008)
Definitions: The arboricity of a graph G, written ϒ(G), is the minimum number of forests whose union is G. The thickness of a graph G, written θ(G), is the minimum number of planar graphs whose union is G. The arboricity ratio of G, written r(G), is ϒ(G)/θ(G).
Background: For every graph G, covering G requires covering all subgraphs, and hence ϒ(G)≥maxH⊆ G⌈|E(H)|/(|V(H)|-1)⌉. Nash-Williams [N] proved that equality always holds. The arboricity formula, when combined with Euler's Formula, implies that every planar graph has arboricity at most 3, and triangle-free planar graphs have arboricity at most 2. Also every forest is planar. Thus 1≤r(G)≤3 in general, and 1≤r(G)≤2 for triangle-free graphs.
For complete graphs and complete bipartite graphs, high density allows the edges to be grouped into maximal planar or maximal triangle-free planar graphs, respectively, so that θ(Kn) = ⌈|E(Kn)|/(3n-6)⌉ = ⌈(n+1)/6⌉ (except K9 and K10) and θ(Kp,p) = ⌈p²/(4p-4)⌉ = ⌈(p+2)/4⌉, Meanwhile, also there are decompositions into spanning trees, so that ϒ(Kn)=⌈n/2⌉ and ϒ(Kp,p)=⌈(p+1)/2⌉. Thus, roughly r(Kn)=3 and r(Kp,p)=2.
Question: What lower bound on r(G) is guaranteed by a lower bound on δ(G)/|V(G)|? For example, if the degree ratio is at least 1/2, does it follow that r(G)≥ 2-o(n-1)? If the degree ratio is at least 2/3, does it follow that r(G)≥ 3-o(n-1)?
References:
[N] Nash-Williams, C. St. J. A.:
Decomposition of finite graphs into forests.
J. London Math. Soc. 39 1964 12.