Fragile minor-monotone parameters under random edge perturbation


الملخص بالإنكليزية

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases.

تحميل البحث