On fractional fragility rates of graph classes (Q2205120)

Summary: We consider, for every positive integer \(a\), probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most \(1/a\). Among other results, we prove that for every positive integer \(a\) and every planar graph \(G\), there exists such a probability distribution with the additional property that for any set \(X\) in the support of the distribution, the graph \(G-X\) has component-size at most \((\Delta(G)-1)^{a+O(\sqrt{a})}\), or treedepth at most \(O(a^3\log_2(a))\). We also provide nearly-matching lower bounds.