The k-strong induced arboricity of a graph

However, we prove that for any proper minor-closed graph class C, and more generally for any class of bounded expansion, and any k⩾1, the maximum value of fk(G) for G∈C is bounded from above by a constant depending only on 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 f2(G)⩽3t+13 for any graph G of tree-width t and that fk(G)⩽(2k)d for any graph of tree-depth d. In addition, we prove that f2(G)⩽310 when G is planar.