Veröffentlichung

Titel:

Induced and weak-induced arboricities

AutorInnen:

Maria Axenovich
Philip Doerr
Jonathan Rollin
Torsten Ueckerdt

Kategorie:

Artikel in Zeitschriften

erschienen in:

Discrete Mathematics, Vol. 342, No. 2, pp. 511–519, 2019

Abstract:

We define the induced arboricity of a graph G, denoted by ia(G), as the smallest k such that the edges of G can be covered with k induced forests in G. For a class F of graphs and a graph parameter p, let p(F)=sup{p(G)∣G∈F}. We show that ia(F) is bounded from above by an absolute constant depending only on F, that is ia(F)≠∞ if and only if χ(F∇1/2)≠∞, where F∇1/2 is the class of 1/2-shallow minors of graphs from F and χ is the chromatic number. As a main contribution of this paper, we provide bounds on ia(F) when F is the class of planar graphs, the class of d-degenerate graphs, or the class of graphs having tree-width at most d. Specifically, we show that if F is the class of planar graphs, then 8≤ia(F)≤10. In addition, we establish similar results for so-called weak induced arboricities and star arboricities of classes of graphs.

Download:

arXiv

BibTeX-Eintrag:

@article{DM2019, author = {Maria Axenovich and Philip D{\"{o}}rr and Jonathan Rollin and Torsten Ueckerdt}, title = {Induced and Weak Induced Arboricities}, journal = {Discrete Mathematics}, volume = {342}, number = {2}, pages = {511-519}, year = {2019}, }