![](/files/happy5.png)
Fox, Jacob
Complete bipartite subgraphs of perfect graphs ★★
Author(s): Fox
Problem Let
be a perfect graph on
vertices. Is it true that either
or
contains a complete bipartite subgraph with bipartition
so that
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \bar{G} $](/files/tex/1e3dac00cfbbb43d9181a85bc8a5389e16490552.png)
![$ (A,B) $](/files/tex/e0150654d2f6aa6b2ea50e726af4747878a605fc.png)
![$ |A|, |B| \ge n^{1 - o(1)} $](/files/tex/457f19bbb97576457ac692bc6acdd4ac8e9f39a1.png)
Keywords: perfect graph
Long rainbow arithmetic progressions ★★
Author(s): Fox; Jungic; Mahdian; Nesetril; Radoicic
For let
denote the minimal number
such that there is a rainbow
in every equinumerous
-coloring of
for every
Conjecture For all
,
.
![$ k\geq 3 $](/files/tex/c403b537b372cb5d16b6129dce0f0c416c1f1b31.png)
![$ T_k=\Theta (k^2) $](/files/tex/861c6fb3fc588a2247540bcd7bf32e42032ad265.png)
Keywords: arithmetic progression; rainbow
![Syndicate content Syndicate content](/misc/feed.png)