In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. More precisely, for an arbitrary undirected graph
H
, let
F
H
be the family of graphs that do not have
H
as an induced subgraph. Then, according to the conjecture, there exists a constant
δ
H
>
0
such that the
n
-vertex graphs in
F
H
have either a clique or an independent set of size
Ω
(
n
δ
H
)
.
An equivalent statement to the original conjecture is that, for every graph
H
, the
H
-free graphs all contain arbitrarily large perfect induced subgraphs.
In contrast, for random graphs in the Erdős–Rényi model with edge probability 1/2, both the maximum clique and the maximum independent set are much smaller: their size is proportional to the logarithm of
n
, rather than growing polynomially. Ramsey's theorem proves that no graph has both its maximum clique size and maximum independent set size smaller than logarithmic. Ramsey's theorem also implies the special case of the Erdős–Hajnal conjecture when
H
itself is a clique or independent set.
This conjecture is due to Paul Erdős and András Hajnal, who proved it to be true when
H
is a cograph. They also showed, for arbitrary
H
, that the size of the largest clique or independent set grows superlogarithmically. More precisely, for every
H
there is a constant
c
such that the
n
-vertex
H
-free graphs have cliques or independent sets containing at least
exp
c
log
n
vertices. The graphs
H
for which the conjecture is true also include the four-vertex path graph, the five-vertex bull graph, and any graph that can be obtained from these and the cographs by modular decomposition. As of 2014, however, the full conjecture has not been proven, and remains an open problem.
An earlier formulation of the conjecture, also by Erdős and Hajnal and still unsolved, concerns the special case when
H
is a 5-vertex cycle graph. The
C
5
-free graphs include the perfect graphs, which necessarily have either a clique or independent set of size proportional to the square root of their number of vertices. Conversely, every clique or independent set is itself perfect. For this reason, a convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph
H
, the
H
-free graphs necessarily contain an induced perfect subgraph of polynomial size.
