Sublinear separators imply fractional treewidth-fragility
Informal Conjecture (fractional treewidth-fragility of sublinear-separator classes) · arXiv:2103.08698
Status open high confidence
Dvořák conjectures in arXiv:2103.08698 that all classes with sublinear separators are fractionally treewidth-fragile. The paper itself establishes the property for hereditary classes with sublinear separators and bounded maximum degree, for all proper minor-closed classes, and for several geometric graph classes, but the full conjecture without the bounded-degree restriction remains open. No follow-up paper proving or disproving the general statement was found across multiple targeted searches.
Reviewer notes. The conjecture is stated informally in the paper: the bounded-degree case is proved therein, as are proper minor-closed classes and geometric classes. The gap is the general sublinear-separator case without bounded degree. Related work (arXiv:2208.10074 on product structure for strongly-sublinear-separator classes) does not address fractional treewidth-fragility. No resolution found in the literature as of 2026-05-15.
Context
The author notes that efficiently fractionally treewidth-fragile classes include all hereditary classes with sublinear separators and bounded maximum degree, all proper minor-closed classes, and many geometric graph classes. The author then remarks that it is possible, and has been conjectured by them, that the property extends to all classes with sublinear separators.
Notes. Stated in running prose as 'it is possible (and I have conjectured) that all classes with sublinear separators are fractionally treewidth-fragile'.
Source paper
Approximation metatheorems for classes with bounded expansion
Zdeněk Dvořák · 2021-10-09
https://arxiv.org/abs/2103.08698
PDF source