Cheap balanced separator conjecture for graphs with polynomial expansion
Cheap balanced separator conjecture for graphs with polynomial expansion
Let be a graph and let be a polynomial such that the expansion of is bounded by . A cost assignment is a function
For integers and , a set is -cheap with outliers if there is a set with and
Here, a balanced separator is a vertex set whose deletion leaves components satisfying the balance condition used in the paper. Cheap balanced separator conjecture. For every polynomial , there exists a function such that, for every graph with expansion bounded by and every cost assignment , each integer admits a balanced separator that is -cheap with outliers. This is a weakening of the conjecture that graphs with polynomial expansion are fractionally treewidth-fragile; the conclusion is therefore known for every class known to be fractionally treewidth-fragile, but the stated conjecture is not resolved in general.
Sources & referencesView supporting material
Primary source
Zdeněk Dvořák, “On weighted sublinear separators”, arXiv:2007.11853 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.