3
$\begingroup$

I am currently doing research on string graphs. A graph $G = (V,E)$ with vertices $V = \{v_1,\ldots,v_n\}$ is called a string graph if there exists a representation of the vertices as continuous curves in the plane $\{\gamma_1,\ldots,\gamma_n\}$ such that $\gamma_i$ and $\gamma_j$ intersect if and only if $i$ and $j$ are connected in $G$, i.e., $ij \in E$. See also https://en.wikipedia.org/wiki/String_graph.

In particular, I am searching for a string graph in which every vertex has degree at least 4 and in which the length of the shortest cycle (girth) is at least 5, or for a proof that such a graph does not exist. Note that the Robertson graph (https://en.wikipedia.org/wiki/Robertson_graph) does have the right minimum degree and girth, but so far I have been unable to prove whether this is a string graph or not.

Does anyone have a clue as to what such a graph should look like or why it would be impossible to make one? I have tried using the crossing number inequality or an application of Kuratowski's Theorem to show that a string representation of such a graph cannot be made to work, but so far to no avail. Any thoughts are greatly appreciated!

$\endgroup$

1 Answer 1

1
$\begingroup$

There are some results in this direction, but it looks like this is still an open problem.

For circle graphs, this bound is just barely false. The Wikipedia page on circle graphs has a beautiful diagram of a circle graph with girth $4$ and minimum degree $5$. On the other hand, Ageev (1999) shows that any circle graph with girth $5$ has minimum degree $3$ or less.

For general string graphs, there is a surprising connection to cops-and-robbers games. Gavenčiak et al. (2015) show that the maximum cop number of a string graph is between $3$ and $15$, and observe that this implies that no string graph can have girth $5$ and minimum degree $16$: on any such graph, the robber always has at least $16$ escape routes, and no cop can block two of them, so $15$ cops cannot block all of them.

At the very least, this implies that there's no easy construction of a string graph with girth $5$ and minimum degree $4$ that the authors of that paper could find: the same argument would show that it is a string graph with cop number $4$, improving their lower bound. (As it is, I think their lower bound comes from planar graphs, which are known to have maximum cop number $3$.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .