Fox, Jacob

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

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

\begin{problem} Let $G$ be a perfect graph on $n$ vertices. Is it true that either $G$ or $\bar{G}$ contains a complete bipartite subgraph with bipartition $(A,B)$ so that $|A|, |B| \ge n^{1 - o(1)}$? \end{problem}

Keywords: perfect graph

Long rainbow arithmetic progressions ★★

Author(s): Fox; Jungic; Mahdian; Nesetril; Radoicic

For $k\in \mathbb{N}$ let $T_k$ denote the minimal number $t\in \mathbb{N}$ such that there is a rainbow $AP(k)$ in every equinumerous $t$-coloring of $\{ 1,2,\ldots ,tn\}$ for every $n\in \mathbb{N}$

\begin{conjecture} For all $k\geq 3$, $T_k=\Theta (k^2)$. \end{conjecture}

Keywords: arithmetic progression; rainbow

Syndicate content