← All problems

Fox–Pach string-graph separator conjecture

There exists a universal constant C>0C>0 such that every finite string graph GG with n≥2n\ge 2 vertices and mm edges has a vertex set S⊆V(G)S\subseteq V(G) satisfying ∣S∣≤Cm|S|\le C\sqrt{m} and such that every connected component of G−SG-S has at most 2n/32n/3 vertices. Here, a string graph is the intersection graph of a finite family of continuous curves in R2\mathbb{R}^2.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

The conjecture was proved years ago,, although that encoding has not been independently assessed.

Fox and Pach conjectured that every string graph with mm edges has a balanced separator of size O(m)O(\sqrt{m}). 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 O(m3/4log⁡m)O(m^{3/4}\sqrt{\log m}), together with the O(m)O(\sqrt{m}) conjecture.
  • Matoušek: an O(mlog⁡m)O(\sqrt{m}\log m) bound for every mm-edge string graph.
  • Lee (2017): every mm-edge string graph has a balanced separator of size O(m)O(\sqrt{m}); 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 O(m)O(\sqrt{m}) separators, polynomial-time algorithms, extensions beyond string graphs, repairs to results affected by a flaw,.

Sources

Solutions 0

No solutions have been posted yet.