Complete bipartite subgraphs of perfect graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite simple graph $G$ is perfect if every induced subgraph $H$ satisfies $\chi(H)=\omega(H)$, where these are chromatic and clique numbers. A complete bipartite subgraph with parts $A,B$ consists of disjoint vertex sets for which every vertex of $A$ is adjacent to every vertex of $B$; edges inside the parts are irrelevant. Let $\overline G$ denote the complement.

Statement recorded in the supplied source.

Is it true that for every $\varepsilon>0$ there is $n_0(\varepsilon)$ such that, for every perfect graph $G$ on $n\ge n_0(\varepsilon)$ vertices, one of $G,\overline G$ has a complete bipartite subgraph with $|A|,|B|\ge n^{1-\varepsilon}$? This is the uniform asymptotic meaning of the source's $n^{1-o(1)}$ bound. [S2]

Short English statement

Does every large perfect graph or its complement contain a balanced complete bipartite subgraph of nearly linear size?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3153 (OPG-826). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Complete bipartite subgraphs of perfect graphs, original node 826, statement and mathematical discussion. https://www.openproblemgarden.org/op/complete_bipartite_subgraphs_of_perfect_graphs.