Publication at Faculty of Mathematics and Physics |
2020
Abstract
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 a).
We also provide nearly-matching lower bounds.