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.
It is named for Paul Erdős and András Hajnal, who first posed it as an open problem in a paper from 1977.
[1] More precisely, for an arbitrary undirected graph
Then, according to the conjecture, there exists a constant
have either a clique or an independent set of size
In other words, for any hereditary family
of graphs that is not the family of all graphs, there exists a constant
have either a clique or an independent set of size
A convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph
-free graphs necessarily contain a perfect induced subgraph of polynomial size.
This is because every perfect graph necessarily has either a clique or independent set of size proportional to the square root of their number of vertices, and conversely every clique or independent set is itself perfect.
Background on the conjecture can be found in two surveys, one of András Gyárfás and the other of Maria Chudnovsky.
[2][3] 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
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
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
, that the size of the largest clique or independent set grows superlogarithmically.
-free graphs have cliques or independent sets containing at least
for which the conjecture is true also include those with four verticies or less, all five-vertex graphs,[5][6][7][8] and any graph that can be obtained from these and the cographs by modular decomposition.
[9] As of 2024, 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, concerns the special case when
[2] This case has been resolved by Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl.
[7] Alon et al. [9] showed that the following statement concerning tournaments is equivalent to the Erdős–Hajnal conjecture.
denotes the chromatic number of
satisfies this equivalent Erdős–Hajnal conjecture (with
, called heroes, were considered by Berger et al.[10] There it is proven that a hero has a special structure which is as follows: Here
denotes the tournament with the three components
, the transitive tournament of size
The arcs between the three components are defined as follows: