![](/files/happy5.png)
Complete bipartite subgraphs of perfect graphs
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)
Every perfect graph on vertices either has a clique or an independent set of size
, so weakening the bound on
,
to
gives a true statement. Jacob Fox [F] has proved that every comparability graph
on
vertices has a complete bipartite subgraph of size
, and (up to the constant) this is best possible.
Bibliography
[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: http://web.math.princeton.edu/~pds/papers/pure5/paper.pdf (not on ArXiv nor published yet)