Fixed-radius coarse separator strengthening

About 1 year old · traced to

Let GG be a graph. For r∈Nr\in\mathbb{N}, an rr-cover of a set S⊆V(G)S\subseteq V(G) is a set S^⊆V(G)\hat{S}\subseteq V(G) such that S⊆NGr[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)→R≥0w: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,r∈Nk,r\in\mathbb{N}, there exists k′∈Nk'\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 r′r'. The source presents it as an additional statement of interest; no resolution is given.

References

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.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.