Pach, János

Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

\begin{conjecture} If $G$ is a simple triangle-free graph, then there is a set of at most $n^2/25$ edges whose deletion destroys every odd cycle. \end{conjecture}


Separators in string graphs ★★

Author(s): Fox; Pach; Tóth

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

Keywords: separator; string graphs

Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

\begin{problem} Does the following equality hold for every graph $G$? \[ \text{pair-cr}(G) = \text{cr}(G) \] \end{problem}

The \Def[crossing number]{Crossing number (graph theory)} $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the \emph{pairwise crossing number} $\text{pair-cr}(G)$, we minimize the number of pairs of edges that cross. %and the \emph{odd-crossing number} $(\text{odd-cr}(G))$ counts the minimum %number of pairs of edges that cross an odd number of times.

Keywords: crossing number; pair-crossing number

Syndicate content