Complete bipartite subgraphs of perfect graphs

Importance: Medium ✭✭

Author(s):

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.