Obstructions for partitioning into forests and outerplanar graphs (Q831856)

The article introduces new parameters which, in a sense, measure ``how far'' a graph \(G\) is from a graph class \(\mathcal{C}\). They consider: \par i) \(\mathcal{C}\)-edge-brittleness \(\eta_{\mathcal{C}}(G)\), which is defined as the minimum \(\ell\) such that \(G\) can be vertex-partitioned into graphs of \(\mathcal{C}\) with \(\ell\) edges having ends in distinct parts, \par ii) \(\mathcal{C}\)-vertex-brittleness \(\kappa_{\mathcal{C}}(G)\), which is defined as the minimum \(\ell\) such that \(G\) can be edge-partitioned into graphs of \(\mathcal{C}\), and only \(\ell\) vertices of \(G\) belong to different such graphs, \par iii) \(\overline{\mathcal{C}}\)-capacity \(\nu_{\mathcal{C}}(G)\), which is defined as the maximum \(\ell\) such that there are \(\ell\) edge-disjoint subgraphs \(H_i\) of \(G\), none of which belongs to \(\mathcal{C}\). For monotone classes \(\mathcal{C}\) (graph classes which are closed under taking subgraphs) which are also closed under taking disjoint unions, they compare these parameters with the usual edit distance (defined as the minimum number of edges needed to transform \(G\) into some graph in \(\mathcal{C}\)), which is a classic way to measure distance to a graph class. Then they study the behaviour of \(\eta_{\mathcal{C}}(G)\), \(\kappa_{\mathcal{C}}(G)\), \(\nu_{\mathcal{C}}(G)\) in more detail whenever the class \(\mathcal{C}\) in question is the class \(\mathcal{A}\) of forests, the class \(\mathcal{O}\) of outerplanar graphs, and the class \(\mathcal{D}\) of diamond-free graphs, i.e. the class of graphs with no diamond as a topological minor (this class is sandwiched between the two previously mentioned classes). For these graph classes \(\mathcal{C}\), they investigate if the parameters \(\eta_{\mathcal{C}}(G)\), \(\kappa_{\mathcal{C}}(G)\), \(\nu_{\mathcal{C}}(G)\) are uniformly bounded whenever the graph \(G\) belongs to an ideal, i.e. a graph class \(\mathcal{G}\) which is closed under taking topological minors. The main interest is to determine for which ideals \(\mathcal{G}\) the value \(\eta_{\mathcal{C}}(G)\), \(\kappa_{\mathcal{C}}(G)\), \(\nu_{\mathcal{C}}(G)\) are bounded independently of the choice of \(G \in \mathcal{G}\), and to identify the ``obstructions'' which preclude this to happen. As their main result, for \(\mathcal{C} \in \{ \mathcal{A}, \mathcal{D} \}\), there is a precise characterisation of the ideals \(\mathcal{G}\) which have uniformly bounded \(\eta_{\mathcal{C}}(G)\), \(\kappa_{\mathcal{C}}(G)\), \(\nu_{\mathcal{C}}(G)\) for \(G \in \mathcal{G}\). For the class \(\mathcal{O}\) they find precisely the minimal ideals \(\mathcal{G}\) which have unbounded \(\kappa_{\mathcal{O}}(G)\) for \(G \in \mathcal{G}\). In all of these results, the ``minimal obstructions'' to have bounded \(\eta_{\mathcal{C}}(G)\), \(\kappa_{\mathcal{C}}(G)\), \(\nu_{\mathcal{C}}(G)\) can be described in terms of graphs of the form \(\operatorname{Fan}(G,S,k)\). Here, \(G\) is a graph, \(S\) is a proper subset of \(V(G)\) and \(k\) is an integer, and \(\operatorname{Fan}(G,S,k)\) is formed by taking \(k\) disjoint copies of \(G\) and then identifying vertices and edges in \(G[S]\). Finally, the authors show that if \(\mathcal{C}\) is an ideal, then \(\kappa_{\mathcal{C}}(G)\), \(\nu_{\mathcal{C}}(G)\) and the edit distance of \(G\) to \(\mathcal{C}\) can only decrease if \(G\) is replaced by a topological minor \(G^\prime\) of \(G\).