Fixed-radius coarse separator strengthening

From papers

Let GG be a graph. For rNr\in\mathbb{N}, an rr-cover of a set SV(G)S\subseteq V(G) is a set S^V(G)\hat{S}\subseteq V(G) such that SNGr[S^]S\subseteq N^r_G[\hat{S}]. A set is (k,r)(k,r)-coverable if it has an rr-cover of size at most kk. The graph GG admits (k,r)(k,r)-balanced separators if, for every weight function w:V(G)R0w:V(G)\to\mathbb{R}_{\geq 0}, it has a (k,r)(k,r)-coverable ww-balanced separator. A tree decomposition is (k,r)(k',r)-coverable if every bag is (k,r)(k',r)-coverable.

Fixed-radius coarse separator strengthening. For every k,rNk,r\in\mathbb{N}, there exists kNk'\in\mathbb{N} such that if GG admits (k,r)(k,r)-balanced separators, then GG admits a (k,r)(k',r)-coverable tree decomposition.

This strengthens the preceding conjecture by requiring the radius of the tree-decomposition bags to remain exactly rr, rather than allowing a new radius rr'. 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

No solutions have been posted yet.