![](/files/happy5.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ \delta(H) $](/files/tex/f3109c2657867bfbf5df1f9d878be062ffaa82d0.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ |V(G)|^{\delta(H)} $](/files/tex/e12fe74b562523df4457275a178e2078c43c7715.png)
There are numerous interesting classes of graphs which are based upon forbidding one or more induced subgraphs. For instance: chordal graphs, split graphs, and claw-free graphs. Numerous other natural classes of graphs have been proved to have such characterizations, most famously perfect graphs, but also line graphs and comparability graphs. All of these classes are very well structured (far from random) and their members all either have large cliques or independent sets. On the flip side of this are random graphs. It is well known that a random graph on vertices has both clique and independence number highly concentrated around
. The Erdos-Hajnal conjecture suggests a fundamental separation between these two worlds in terms of independence/clique sizes.
Erdös and Hajnal proved that this conjecture is true for the recursive class of graphs defined as follows. The one vertex graph is in
, and if
and
lie in
, then the disjoint union of
and
lies in
, as does the graph obtained from the disjoint union by adding an edge between
and
for every
and
. More generally, Alon, Pach, and Solymosi proved that if
is a graph with
for which the Erdös-Hajnal conjecture holds, and
are graphs for which the Erdos-Hajnal conjecture holds, then the graph obtained from
by blowing up each vertex
with a copy of
(more precisely, starting from the disjoint union of
, we add all possible edges between the vertices of
and
if
) also satisfies the Erdos-Hajnal conjecture.
The Erdös-Hajnal property is known to hold for a number of small graphs (and using the above result this may be easily bootstrapped). For instance, the conjecture is known to hold when is a path of three edges, and recently M. Chudnovsky and S. Safra have announced a proof when
is a bull (a triangle plus two pendant edges). However, our knowledge here is still quite limited. In particular, Lovasz has suggested the following very special case which remains open.
![$ H \cong C_5 $](/files/tex/0680ae7418e714b3877dd7a02badc4c90fd9ed88.png)
Bibliography
[APS] N. Alon, J. Pach, and J. Solymosi, Ramsey-type theorems with forbidden subgraphs, Combinatorica 21 (2001), 155-170.
[EH] P. Erdös and A. Hajnal, Ramsey-type theorems, Discrete Appl. Math. 25 (1989), 37-52 MathSciNet
* indicates original appearance(s) of problem.