Can I read On Fractional Fragility Rates of Graph Classes on EtoBox?

On Fractional Fragility Rates of Graph Classes by Dvořák, Zdeněk; Sereni, Jean-Sébastien is a scholarly article available to read on EtoBox.

What is On Fractional Fragility Rates of Graph Classes about?

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 deleting the random set creates a graph with component-size at most $(\Delta(G)-1)^{a+O(\sqrt{a})}$, or a graph with treedepth at most $O(a^3\log_2(a))$. We also provide nearly-matching lower bounds.

Author

Dvořák, Zdeněk; Sereni, Jean-Sébastien

Published

2019

Language

EN