Obstructions for partitioning into forests and outerplanar graphs

Abstract

For a class $\mathcal{C}$ of graphs, we define $\mathcal{C}$-edge-brittleness of a graph $G$ as the minimum $\ell$ such that the vertex set of $G$ can be partitioned into sets inducing a subgraph in $\mathcal{C}$ and there are $\ell$ edges having ends in distinct parts. We characterize classes of graphs having bounded $\mathcal{C}$-edge-brittleness for a class $\mathcal{C}$ of forests or a class $\mathcal{C}$ of graphs with no $K_4\setminus e$ topological minors in terms of forbidden obstructions. We also define $\mathcal{C}$-vertex-brittleness of a graph $G$ as the minimum $\ell$ such that the edge set of $G$ can be partitioned into sets inducing a subgraph in $\mathcal{C}$ and there are $\ell$ vertices incident with edges in distinct parts. We characterize classes of graphs having bounded $\mathcal{C}$-vertex-brittleness for a class $\mathcal{C}$ of forests or a class $\mathcal{C}$ of outerplanar graphs in terms of forbidden obstructions. We also investigate the relations between the new parameters and the edit distance.

28 pages, 8 figures. Accepted to Discrete Appl. Math., 2020