Fox–Pach separator conjecture for string graphs

A string graph is the intersection graph of a collection of curves in the plane. A separator in a graph G=(V,E)G=(V,E) is a subset SVS\subseteq V such that no connected component of GSG\setminus S has more than 23V\frac{2}{3}|V| vertices. Fox–Pach's separator conjecture. Every string graph with mm edges has a separator of order

O(m).O(\sqrt{m}).

This would remove the logarithmic factor from the previously known separator bound and would yield improvements to the paper's applications, including stronger edge bounds for Kt,tK_{t,t}-free string graphs.

Sources & referencesView supporting material

Primary source

Jacob Fox and Janos Pach, “Applications of a new separator theorem for string graphs”, arXiv:1302.7228 (2013).

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.