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
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.

Claimed to be solved

In this recent preprint on Paul Seymour's webpage: (not on ArXiv nor published yet)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.