Veröffentlichung

Titel:

The k-strong induced arboricity of a graph

AutorInnen:

Maria Axenovich
Daniel Goncalves
Jonathan Rollin
Torsten Ueckerdt

Kategorie:

Artikel in Zeitschriften

erschienen in:

European Journal of Combinatorics, Vol. 67, pp. 1–20, 2018

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⩾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 C, and more generally for any class of bounded expansion, and any k⩾1, the maximum value of f_k(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 f₂(G)⩽(t+1)t(t-1)/2 for any graph G of tree-width t and that f_k(G)⩽(2k)^d for any graph of tree-depth d. In addition, we prove that f₂(G)⩽310 when G is planar.

Download:

arXiv

BibTeX-Eintrag:

@article{, author = {Maria Axenovich and Daniel Gon{\c{c}}alves and Jonathan Rollin and Torsten Ueckerdt}, title = {The k-strong induced arboricity of a graph}, journal = {Eur. J. Comb.}, volume = {67}, pages = {1--20}, year = {2018}, url = {https://doi.org/10.1016/j.ejc.2017.05.010}, doi = {10.1016/j.ejc.2017.05.010}, }