The balanced separator conjecture for sphere intersection graphs
The balanced separator conjecture for sphere intersection graphs
Let be integers, and let be an -vertex graph in the class of sphere intersection graphs. A balanced separator is a vertex set whose removal leaves no connected component with more than a fixed balanced fraction of the vertices. Balanced separator conjecture. Every such graph has a balanced separator of size
The conjecture would improve the exponent in the known separator theorem for sphere intersection graphs. It is known for , while the general case remains open.
Sources & referencesView supporting material
Primary source
James Davies, Agelos Georgakopoulos, Meike Hatzel and Rose McCarty, “Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs”, arXiv:2504.00932 (2025).
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.