Separators in string graphs

Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: cibulka
on: January 1st, 2010

\begin{conjecture} Every string graph with $m$ edges has a separator of size $O(\sqrt{m})$. \end{conjecture}

Consider a graph $G=(V,E)$ with vertex weights $w:V \rightarrow \mathbb R_{\geq 0}$. A separator in $G$ is a set $S$ of vertices such that there is a partition $V=C_1 \cup S \cup C_2$ of the vertices with no edge going between $C_1$ and $C_2$ and with $w(C_1),w(C_2)\leq 2/3$. The size of the separator $S$ is the number of vertices of $S$.

The result holds for planar graphs (which form a subclass of string graphs) by the \Def[Lipton-Tarjan theorem]{Planar_separator_theorem}~[LT]. The best known upper bound for string graphs is currently $O(m^{3/4} \sqrt{\log(m)})$ from~[FP].

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

*[FPT] Jacob Fox, János Pach, Csaba D. Tóth: \href[Intersection patterns of curves]{http://www.princeton.edu/~jacobfox/papers/foxpachto.pdf}, J. London Math. Soc., to appear

[FP] Jacob Fox, János Pach \href[A separator theorem for string graphs and its applications]{http://www.princeton.edu/~jacobfox/papers/foxpach.pdf}, Combinatorics, Probability and Computing, to appear.

[LT] Richard J. Lipton, Robert Endre Tarjan: \href[A separator theorem for planar graphs]{http://www.cs.princeton.edu/courses/archive/fall06/cos528/handouts/sepplanar.pdf}, SIAM Journal on Applied Mathematics 36 (1979), 177-–189.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.

Jiri Matousek has almost

Jiri Matousek has almost solved this problem. He proves a $O(\sqrt m \log m)$ upper bound in "Near-optimal separators in string graphs" at arXiv:1302.6482.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.