The Erdős–Hajnal conjecture for bull-free graphs

The bull is a graph consisting of a triangle and two pendant edges. A graphs is called bull-free if no induced subgraph of it is a bull. In this paper we prove that every bull-free graph on n vertices contains either a clique or a stable set of size n 1 4 , thus settling the Erdős–Hajnal conjecture [P. Erdős, A. Hajnal, Ramsey-type theorems, Discrete Appl. Math. 25 (1989) 37–52] for the bull.