Fox–Pach string-graph separator conjecture
There exists a universal constant such that every finite string graph with vertices and edges has a vertex set satisfying and such that every connected component of has at most vertices. Here, a string graph is the intersection graph of a finite family of continuous curves in .
References
- Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs — arXiv — James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak
Source: arXiv
Progress summary
The conjecture was proved years ago,, although that encoding has not been independently assessed.
Fox and Pach conjectured that every string graph with edges has a balanced separator of size . Their conjecture has since been confirmed, with the bound extended to broader region-intersection graph classes.
Known results
- Fox and Pach: an earlier separator bound of , together with the conjecture.
- Matoušek: an bound for every -edge string graph.
- Lee (2017): every -edge string graph has a balanced separator of size ; the proof is constructive and yields a polynomial-time algorithm.
- The square-root bound is optimal up to constants.
A new preprint by James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, and Bartosz Walczak reports separators, polynomial-time algorithms, extensions beyond string graphs, repairs to results affected by a flaw,.
Solutions 0
No solutions have been posted yet.