arXiv:2611.21961v1 Announce Type: new Abstract: The blob graph $G^\circ$ of a graph $G$ has a vertex for each non-empty connected vertex subset of $G$, with two distinct subsets adjacent whenever they intersect or are joined by an edge of $G$. This construction has been used in reductions from induced subgraph optimisation problems to maximum-weight independent set, where the preservation of forbidden substructures is essential. We completely characterise the graphs $H$ for which excluding $H$ from $G$ guarantees that $G^\circ$ also excludes $H$, under six containment relations. For subgraphs, minors, and topological minors, preservation holds exactly when $H$ has at most two vertices. For induced subgraphs, it holds exactly when $H$ is a linear forest. For induced topological minors, it holds exactly when $H$ is triangle-free and has maximum degree at most two. For induced minors, it holds exactly when $H$ is triangle-free and every neighbour of a vertex of degree at least three has degree exactly two. These classifications unify and extend preservation results previously established for particular forbidden graphs in algorithmic applications.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page