Importance: Medium ✭✭
Author(s): Fox, Jacob
Keywords: perfect graph
Recomm. for undergrads: no
Posted by: mdevos
on: June 17th, 2008
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)} $?

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, A Bipartite Analogue of Dilworth’s Theorem, Order 23 (2006), 197-209.

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options