Home » Subject » Graph Theory » Basic G.T.
Importance: Medium ✭✭
Author(s): Fox, Jacob
Subject: Graph Theory
» Basic Graph Theory
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.

Bibliography

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


* indicates original appearance(s) of problem.
1 comment

Reply

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