Complete bipartite subgraphs of perfect graphs

Importance: Medium ✭✭
Author(s): Fox, Jacob
Keywords: perfect graph
Recomm. for undergrads: no
Posted by: mdevos
on: June 17th, 2008

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

Every perfect graph on $n$ vertices either has a clique or an independent set of size $\ge n^{1/2}$, so weakening the bound on $|A|$, $|B|$ to $\lfloor \frac{1}{2} n^{1/2} \rfloor$ gives a true statement. Jacob Fox [F] has proved that every comparability graph $G$ on $n$ vertices has a complete bipartite subgraph of size $\ge c \frac{n}{\log n}$, and (up to the constant) this is best possible.


[F] J. Fox, \href[A Bipartite Analogue of Dilworth’s Theorem]{}, Order 23 (2006), 197-209.

* indicates original appearance(s) of problem.