Fox–Pach separator conjecture for string graphs
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 is a subset such that no connected component of has more than vertices. Fox–Pach's separator conjecture. Every string graph with edges has a separator of order
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 -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
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.