Induced and weak induced arboricities

DOI10.1016/J.DISC.2018.10.018MaRDI QIDQ1625812zbMATH OpenOpenAlexWikidataFDO

Authors Philip Dörr, Jonathan Rollin, Torsten Ueckerdt, Maria Axenovich

Publication date 29 November 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.02152

zbMATH Keywords

arboricityedge-coveringinduced forestplanar graphstar forest

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We define the induced arboricity of a graph $G$, denoted by $mia(G)$, as the smallest $k$ such that the edges of $G$ can be covered with $k$ induced forests in $G$. This notion generalizes the classical notions of the arboricity and strong chromatic index. For a class $mathcalF$ of graphs and a graph parameter $p$, let $p(mathcalF)=supp(G)midGinmathcalF$. We show that $mia(mathcalF)$ is bounded from above by an absolute constant depending only on $mathcalF$, that is $mia(mathcalF)eqinfty$ if and only if $chi(mathcalFablafrac12)eqinfty$, where $mathcalFablafrac12$ is the class of $frac12$-shallow minors of graphs from $mathcalF$ and $chi$ is the chromatic number. Further, we give bounds on $mia(mathcalF)$ when $mathcalF$ 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 $mathcalF$ is the class of planar graphs, then $8leqmia(mathcalF)leq10$. In addition, we establish similar results for so-called weak induced arboricities and star arboricities of classes of graphs.

Recommendations

• The \(k\)-strong induced arboricity of a graph
• Inducibility of topological trees
• Induced betweenness in order-theoretic trees
• Induced trees, minimum semidefinite rank, and zero forcing
• Inducibility of \(d\)-ary trees
• scientific article; zbMATH DE number 9665
• Families of induced trees and their intersection graphs
• Induced trees in triangle-free graphs
• Induced trees in triangle-free graphs
• Well-indumatched Trees and Graphs of Bounded Girth

Cites work

• An inequality involving the vertex arboricity and edge arboricity of a graph
• Decomposition of Finite Graphs Into Forests
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. V. Excluding a planar graph
• Graph treewidth and geometric thickness parameters
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• On acyclic colorings of planar graphs
• On forbidden subdivision characterizations of graph classes
• Partitioning graphs of bounded tree-width
• Sparsity. Graphs, structures, and algorithms
• Star arboricity
• Star arboricity of graphs
• The \(k\)-strong induced arboricity of a graph
• The star arboricity of graphs

Cited in

(24)

• Complexity and algorithms for injective edge-coloring in graphs
• Injective edge-coloring of graphs with given maximum degree
• Note on injective edge-coloring of graphs
• Injective edge-coloring of graphs with small weight
• Injective edge chromatic index of generalized Petersen graphs
• Injective edge coloring of sparse graphs with maximum degree 5
• The \(k\)-strong induced arboricity of a graph
• Injective edge coloring for graphs with small edge weight
• scientific article; zbMATH DE number 2111696 (Why is no real title available?)
• Injective edge coloring of graphs
• Injective edge coloring of power graphs and necklaces
• Injective edge-coloring of subcubic graphs
• Complexity and algorithms for injective edge coloring of graphs
• Injective edge coloring of graphs with maximum degree 5
• The injective chromatic index of a claw-free subcubic graph is at most 6
• Injective edge chromatic index of generalized Petersen graph \(P(ck,k)\)
• Injective edge coloring of some standard graph products
• Injective edge-coloring of claw-free subcubic graphs
• On injective edge-coloring of graphs with maximum degree 4
• Injective edge-colorings of K₄-minor free graphs
• Injective edge coloring of sparse graphs
• Injective edge colorings of degenerate graphs and the oriented chromatic number
• Injective edge chromatic index of sparse graphs
• The injective chromatic index of planar graphs with maximum degree 4

This page was built for publication: Induced and weak induced arboricities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1625812)