Claims

../

1989_10_01_erdos_hajnal: Erdős and Hajnal (1989) prove their conjecture for every graph H on at most four vertices, beside the general bound exp(c sqrt(log n)) for every H; accepted on the refereed Discrete Applied Mathematics paper.

2001_04_01_alon_pach_solymosi: Alon, Pach and Solymosi prove that the graphs with the Erdős-Hajnal property are closed under vertex substitution, which with the four-vertex cases settles every graph built from them; accepted on the refereed paper.

2008_06_28_chudnovsky_safra: Chudnovsky and Safra prove that every bull-free graph on n vertices has a clique or a stable set of size at least n^(1/4), the Erdős-Hajnal conjecture for the bull; accepted on the refereed JCTB paper.

2021_02_09_chudnovsky_scott_seymour_spirkl: Chudnovsky, Scott, Seymour and Spirkl prove that for some t > 0 every graph with no induced five-cycle has a clique or a stable set of size at least |G|^t, the Erdős-Hajnal conjecture for C5; accepted on the refereed paper.

2023_07_12_nguyen_scott_seymour: Nguyen, Scott and Seymour prove the Erdős-Hajnal conjecture for every graph whose prime induced subgraphs each have a vertex of degree one and one of degree |H'|-2, a family with infinitely many prime members; refereed (TAMS).

2023_12_23_nguyen_scott_seymour: Nguyen, Scott and Seymour prove the Erdős-Hajnal conjecture for the five-vertex path, which with the earlier cases completes every five-vertex graph; accepted on the refereed Proc. Lond. Math. Soc. paper.

2026_06_04_huang_ju_zhou: Huang, Ju and Zhou (arXiv 2026) claim the Erdős-Hajnal conjecture for two six-vertex graphs, the E-graph and the Bird graph, the first six-vertex cases that do not follow from known operations.

---