The $k$-strong induced arboricity of a graph

Abstract

The induced arboricity of a graph $G$ is the smallest number of induced forests covering the edges of $G$. This is a well-defined parameter bounded from above by the number of edges of $G$ when each forest in a cover consists of exactly one edge. Not all edges of a graph necessarily belong to induced forests with larger components. For $k\ge 1$, we call an edge $k$-valid if it is contained in an induced tree on $k$ edges. The $k$-strong induced arboricity of $G$, denoted by $f_k(G)$, is the smallest number of induced forests with components of sizes at least $k$ that cover all $k$-valid edges in $G$. This parameter is highly non-monotone. However, we prove that for any proper minor-closed graph class $\mathcal{C}$, and more generally for any class of bounded expansion, and any $k\ge 1$, the maximum value of $f_k(G)$ for $G\in \mathcal{C}$ is bounded from above by a constant depending only on $\mathcal{C}$ and $k$. This implies that the adjacent closed vertex-distinguishing number of graphs from a class of bounded expansion is bounded by a constant depending only on the class. We further prove that $f_2(G)\le 3\left(\genfrac{}{}{0ex}{}{t+1}{3}\right)$ for any graph $G$ of tree-width~$t$ and that $f_k(G)\le (2k{)}^d$ for any graph of tree-depth $d$. In addition, we prove that $f_2(G)\le 310$ when $G$ is planar.

24 pages, 11 figures