Fox, Jacob

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

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)}$ ?

Keywords: perfect graph

Posted by mdevos
updated January 19th, 2021

1 comment

Combinatorics

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}$