Leírás
For a graph $G$, the arboricity $a(G)$ is the smallest number of forests covering the edges of $G$. The induced arboricity $ia(G)$ is the smallest number of induced forests of $G$ covering its edges. While the arboricity is a well understood parameter depending on local densities according to Nash-Williams theorem, the induced arboricity has a different nature. For a class of graphs $F$, $ia(F)= \sup\{ia(G):~ G\in F\}$. We characterise classes of graphs for which $ia(F)$ is finite and provide specific bounds on $ia(F)$ for some special classes of graphs, such as planar graphs. In addition, we define a generalised induced arboricity $ia_k(G)$ similarly to the induced arboricity with an additional restriction that each component in each covering forest has size at least $k$. We prove that for any class $F$ of graphs of bounded expansion and any $k$, there is a constant $b_k(F)$ such that $ia_k(G)<b_k(F)$ for any graph $G$ from $F$.
This is a joint work with Daniel Goncalves, Philip Doerr, Jonathan Rollin, and Torsten Ueckerdt