17 problems

Fox–Pach separator conjecture. Every string graph with $m$ edges has a separator of order

Gupta's conjecture. Planar graphs admit embeddings into $\ell_1$ with bounded distortion. Equivalently, string graphs admit embeddings into $\ell_1$ with bounded distortion.

Let $G$ be a string graph drawn in a surface of fixed Euler genus $g$, and let $\Delta$ be the maximum degree of $G$. Polynomial row-treewidth conjecture. The row treewidth of $G$…

Let $\Sigma$ be a surface with Euler genus $g$, and let $G$ be a string graph in $\Sigma$. A string representation $\mathcal{C}$ of $G$ in $\Sigma$ assigns a non-self-intersecting…

A string graph is a graph isomorphic to the intersection graph of a collection of non-self-intersecting continuous curves in a surface, with no three curves crossing at a common po…

Let $G$ be a string graph, let $n$ be its size, and let $\omega(G)$ and $\beta(G)$ denote the parameters used by the source. An $f(\omega(G),\beta(G))$-coloring is a coloring with…

A hereditary class is a graph class closed under induced subgraphs. A string graph is an intersection graph of curves in the plane, and $K_{\ell,\ell}$ is the complete bipartite gr…

Let $s\ge 1$, let $\varepsilon>0$, and let $G$ be the complement of a string graph. Here $\varrho_{4s+1}(G)$ denotes the density of copies of $K_{4s+1}$ in $G$, and $K_{s+1}[t]$ de…

Let $k$ be an integer, and consider the class of string graphs whose odd girth is at least $k$. String-graph coloring conjecture. There is an integer $k$ such that the class of str…

Pach–Tomon conjecture. Their result for string graphs represented by x-monotone curves should remain valid without the assumption that the curves are x-monotone.

EGL coloring conjecture. There is a constant $c$ such that every such family $\mathcal{S}$ is $(k+c)$-colorable.

A 1-intersecting set of strings is a set of strings in which any two strings intersect in at most one point, and it is $k$-touching if every point of the plane belongs to at most…

A touching set of strings is a finite family of strings in the plane in which no pair crosses, and it is $k$-touching if every point of the plane belongs to at most $k$ strings. Li…

For a graph $G$ on $n$ vertices, let $X_n$ be the degree of a uniformly random vertex of $G$. Let $\mathcal{OSG}_n$ and $\mathcal{OSG}^L_n$ denote the classes of unlabeled and labe…

Let $\mathcal{SG}_n$ and $\mathcal{SG}^L_n$ denote, respectively, the classes of unlabeled and labeled string graphs on $n$ vertices, and let $W^4_{1/2}$ be the corresponding graph…

For an integer $t\geq 2$, a graph is $K_{t,t}$-free if it contains no complete bipartite subgraph with $t$ vertices in each part. Fox–Pach's sharp edge bound conjecture. Every…

For an integer $t\geq 2$, a graph is $K_{t,t}$-free if it contains no complete bipartite subgraph with $t$ vertices in each part. Pach–Sharir's linear bound conjecture. There is a…