Fixed-radius coarse separator strengthening
Fixed-radius coarse separator strengthening
Let be a graph. For , an -cover of a set is a set such that . A set is -coverable if it has an -cover of size at most . The graph admits -balanced separators if, for every weight function , it has a -coverable -balanced separator. A tree decomposition is -coverable if every bag is -coverable.
Fixed-radius coarse separator strengthening. For every , there exists such that if admits -balanced separators, then admits a -coverable tree decomposition.
This strengthens the preceding conjecture by requiring the radius of the tree-decomposition bags to remain exactly , rather than allowing a new radius . The source presents it as an additional statement of interest; no resolution is given.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Maria Chudnovsky, Julien Codsi and Claire Kaneshiro, “Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs”, arXiv:2606.14974 (2026).
Additional references
2 papers in this index state this conjecture (2025–2026). The statement above is taken from the most recent of them; the others are arXiv:2505.06550.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.