En théorie des graphes, la conjecture d'Erdős-Hajnal concerne une relation entre les sous-graphes induits et les cliques et stables.