Induced and weak induced arboricities. (English) Zbl 1400.05179
Summary: We define the induced arboricity of a graph \(G\), denoted by \(\mathrm{ia}(G)\), as the smallest \(k\) such that the edges of \(G\) can be covered with \(k\) induced forests in \(G\).
For a class \(\mathcal{F}\) of graphs and a graph parameter \(p\), let \(p(\mathcal{F}) = \sup \{p(G) \mid G \in \mathcal{F} \}\). We show that \(\mathrm{ia}(\mathcal{F})\) is bounded from above by an absolute constant depending only on \(\mathcal{F}\), that is \(\mathrm{ia}(\mathcal{F}) \neq \infty\) if and only if \(\chi(\mathcal{F} \nabla \frac{1}{2}) \neq \infty\), where \(\mathcal{F} \nabla \frac{1}{2}\) is the class of \(\frac{1}{2}\)-shallow minors of graphs from \(\mathcal{F}\) and\(\chi\) is the chromatic number.
As a main contribution of this paper, we provide bounds on \(\mathrm{ia}(\mathcal{F})\) when \(\mathcal{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 \(\mathcal{F}\) is the class of planar graphs, then \(8 \leq \mathrm{ia}(\mathcal{F}) \leq 10\).
In addition, we establish similar results for so-called weak induced arboricities and star arboricities of classes of graphs.
For a class \(\mathcal{F}\) of graphs and a graph parameter \(p\), let \(p(\mathcal{F}) = \sup \{p(G) \mid G \in \mathcal{F} \}\). We show that \(\mathrm{ia}(\mathcal{F})\) is bounded from above by an absolute constant depending only on \(\mathcal{F}\), that is \(\mathrm{ia}(\mathcal{F}) \neq \infty\) if and only if \(\chi(\mathcal{F} \nabla \frac{1}{2}) \neq \infty\), where \(\mathcal{F} \nabla \frac{1}{2}\) is the class of \(\frac{1}{2}\)-shallow minors of graphs from \(\mathcal{F}\) and\(\chi\) is the chromatic number.
As a main contribution of this paper, we provide bounds on \(\mathrm{ia}(\mathcal{F})\) when \(\mathcal{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 \(\mathcal{F}\) is the class of planar graphs, then \(8 \leq \mathrm{ia}(\mathcal{F}) \leq 10\).
In addition, we establish similar results for so-called weak induced arboricities and star arboricities of classes of graphs.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C05 | Trees |
References:
| [1] | Algor, I.; Alon, N., The star arboricity of graphs, Graph Theory and Combinatorics (Cambridge, 1988). Graph Theory and Combinatorics (Cambridge, 1988), Discrete Math., 75, 1-3, 11-22, (1989) · Zbl 0684.05033 |
| [2] | Alon, N.; McDiarmid, C.; Reed, B., Star arboricity, Combinatorica, 12, 4, 375-380, (1992) · Zbl 0780.05043 |
| [3] | Axenovich, M.; Gonçalves, D.; Rollin, J.; Ueckerdt, T., The k-strong induced arboricity of a graph, European J. Combin., 67, 1-20, (2018) · Zbl 1371.05280 |
| [4] | Borodin, O. V., On acyclic colorings of planar graphs, Discrete Math., 25, 3, 211-236, (1979) · Zbl 0406.05031 |
| [5] | Burr, S. A., An inequality involving the vertex arboricity and edge arboricity of a graph, J. Graph Theory, 10, 3, 403-404, (1986) · Zbl 0651.05030 |
| [6] | Ding, G.; Oporowski, B.; Sanders, D. P.; Vertigan, D., Partitioning graphs of bounded tree-width, Combinatorica, 18, 1, 1-12, (1998) · Zbl 0924.05022 |
| [7] | Dörr, P., Induced Arboricity of Planar Graphs, (2017), KIT, (Bachelor’s thesis) |
| [8] | Dujmović, V.; Wood, D. R., Graph treewidth and geometric thickness parameters, Discrete Comput. Geom., 37, 4, 641-670, (2007) · Zbl 1118.05018 |
| [9] | Dvořák, Z., On forbidden subdivision characterizations of graph classes, European J. Combin., 29, 5, 1321-1332, (2008) · Zbl 1151.05038 |
| [10] | Faudree, R.; Gyárfás, A.; Schelp, R.; Tuza, Z., The strong chromatic index of graphs, Ars Combin., 29, 205-211, (1990) · Zbl 0721.05018 |
| [11] | Hakimi, S. L.; Mitchem, J.; Schmeichel, E. F., Star arboricity of graphs, Discrete Math., 149, 1-3, 93-98, (1996) · Zbl 0843.05037 |
| [12] | Nash-Williams, C. S.J. A., Decomposition of finite graphs into forests, J. Lond. Math. Soc., 39, 12, (1964) · Zbl 0119.38805 |
| [13] | J. Nešetřil, P. Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms, vol. 28, Springer Science & Business Media, 2012.; J. Nešetřil, P. Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms, vol. 28, Springer Science & Business Media, 2012. · Zbl 1268.05002 |
| [14] | Robertson, N.; Seymour, P. D., Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322, (1986) · Zbl 0611.05017 |
| [15] | Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41, 92-114, (1986) · Zbl 0598.05055 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
