For every $k$, the class forbidding $P_k$ and $\overline{P_k}$ has the strong Erdős–Hajnal property

We first prove the connected-case claim: for each $r\ge 2$ there are constants ${\epsilon }_r>0$ and $c_r>0$ such that every connected graph $J$ on $m\ge 2$ vertices has a vertex of degree greater than ${\epsilon }_{r}m$, or contains an induced $P_r$ starting at every vertex, or has a biclique of size at least $c_{r}m$ in $\bar{J}$. We prove this by induction on $r$.

For $r=2$, choose ${\epsilon }_2:=1\mathrm{/}2$ and $c_2:=1\mathrm{/}4$. Every vertex of a connected graph on at least two vertices is incident with an edge, so every vertex starts an induced $P_2$. Thus the claim holds for $r=2$.

Fix $r>2$, assume the claim for $r-1$, and let ${\epsilon }_r:={\epsilon }_{r-1}\mathrm{/}(2+{\epsilon }_{r-1})$. Since ${\epsilon }_r<1\mathrm{/}2$, choose any constant $0<c_r\le \min \{(1-2{\epsilon }_r)\mathrm{/}4,c_{r-1}(1-{\epsilon }_r)\mathrm{/}2\}$. Now let $J$ be a connected graph on $m\ge 2$ vertices for which the first outcome fails, so every vertex has degree at most ${\epsilon }_{r}m$. Fix a vertex $v_1$ and put $S:=V(J)\setminus (N_J(v_1)\cup \{v_1\})$. Then $\mathrm{\mid }S\mathrm{\mid }\ge (1-{\epsilon }_r)m-1$. Since $J$ is connected, $v_1$ has degree at least $1$, so $m\ge 1\mathrm{/}{\epsilon }_r$ and therefore $\mathrm{\mid }S\mathrm{\mid }\ge (1-2{\epsilon }_r)m$.

Suppose every connected component of $J[S]$ has size at most $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Choose components greedily until their union $A$ has size in the interval $[\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4,\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2]$: if the running union first reaches $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4$ before it exceeds $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$, stop there; otherwise the next component itself has size in $[\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4,\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2]$ and we take that one alone. Let $B:=S\setminus A$. Then $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }S\mathrm{\mid }\mathrm{/}4$, and [L3] makes $A$ anticomplete to $B$ in $J$. Hence $A$ and $B$ form a biclique of size at least $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4\ge c_{r}m$ in $\bar{J}$.

Suppose instead that $J[S]$ has a connected component $S^{\mathrm{\prime }}$ with $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Because $J$ is connected, some vertex $v_2\in N_J(v_1)$ has a neighbour in $S^{\mathrm{\prime }}$. Let $J_2:=J[S^{\mathrm{\prime }}\cup \{v_2\}]$, which is connected. Every vertex of $J_2$ still has degree at most ${\epsilon }_{r}m$, and ${\epsilon }_{r}m={\epsilon }_{r-1}(1-{\epsilon }_r)m\mathrm{/}2<{\epsilon }_{r-1}(\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }+1)={\epsilon }_{r-1}\mathrm{\mid }V(J_2)\mathrm{\mid }$ because $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }+1>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2+1\ge (1-{\epsilon }_r)m\mathrm{/}2$. So the first outcome of the induction hypothesis is false for $J_2$.

Apply the induction hypothesis to $J_2$ with parameter $r-1$. If outcome 2 holds there, then $J_2$ contains an induced $P_{r-1}$ starting at $v_2$, and prefixing this path with $v_1$ gives an induced $P_r$ in $J$ starting at $v_1$ because $v_1$ is adjacent to $v_2$ and has no neighbours in $S^{\mathrm{\prime }}$. If outcome 3 holds there, then $\overline{J_2}$ contains a biclique of size at least $c_{r-1}\mathrm{\mid }V(J_2)\mathrm{\mid }\ge c_{r-1}(1-{\epsilon }_r)m\mathrm{/}2\ge c_{r}m$, and the same biclique lies in $\bar{J}$. Thus, whenever outcome 1 fails for $J$, either outcome 2 or outcome 3 follows. This completes the induction and proves the connected-case claim.

Let $\epsilon :={\epsilon }_k\mathrm{/}8$. Because $P_k$ is the standard $k$-vertex path, [L1] applied to $H=P_k$ yields a constant $\delta >0$ such that every nonempty $P_k$-free graph has a vertex set of size at least $\delta n$ whose self-density is at most $\epsilon$ or at least $1-\epsilon$.

Let $G$ be a graph with no induced $P_k$ and no induced $\overline{P_k}$, and let $n:=\mathrm{\mid }V(G)\mathrm{\mid }\ge 2$. If $G$ has a set of size at least $\delta n$ and self-density at least $1-\epsilon$, apply the same argument to $\bar{G}$: an induced $P_k$ in $\bar{G}$ would be an induced $\overline{P_k}$ in $G$, and an induced $\overline{P_k}$ in $\bar{G}$ would be an induced $P_k$ in $G$. So $\bar{G}$ belongs to the same forbidden class. Replacing $G$ by $\bar{G}$ if necessary, we may assume that $G$ has a set $S_0$ with $\mathrm{\mid }{S}_0\mathrm{\mid }\ge \delta n$ and self-density at most $\epsilon$.

By [L2], the set $S_0$ contains a subset $S$ with $\mathrm{\mid }S\mathrm{\mid }\ge \mathrm{\mid }{S}_0\mathrm{\mid }\mathrm{/}2\ge \delta n\mathrm{/}2$ such that $S$ is $4\epsilon$-sparse. By [F1], every vertex of $G[S]$ therefore has degree at most $4\epsilon \mathrm{\mid }S\mathrm{\mid }={\epsilon }_k\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$.

If every connected component of $G[S]$ has size at most $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$, then the same greedy argument as in step 4.1 partitions those components into anticomplete sets $A,B\subseteq S$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }S\mathrm{\mid }\mathrm{/}4\ge \delta n\mathrm{/}8$. This is already a pure pair in $G$.

Otherwise $G[S]$ has a connected component $S^{\mathrm{\prime }}$ with $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Every vertex of $G[S^{\mathrm{\prime }}]$ has degree at most ${\epsilon }_k\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2<{\epsilon }_k\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }$, and $G[S^{\mathrm{\prime }}]$ is $P_k$-free because induced subgraphs preserve forbidden induced paths. Applying the connected-case claim from step 5.1 to the connected graph $G[S^{\mathrm{\prime }}]$, outcome 1 is false by the degree bound and outcome 2 is false because $G[S^{\mathrm{\prime }}]$ contains no induced $P_k$ at all. Hence outcome 3 holds, so $\overline{G[S^{\mathrm{\prime }}]}$ has a biclique with both sides of size at least $c_k\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }\ge c_k\delta n\mathrm{/}4$. Equivalently, $G$ has an anticomplete pair of that size.

Let ${\gamma }_k:=\min \{\delta \mathrm{/}8,c_k\delta \mathrm{/}4\}$. Steps 9.1 and 9.2 show that every graph with no induced $P_k$ or $\overline{P_k}$ and at least two vertices contains a pure pair with both sides of size at least ${\gamma }_{k}n$. By [L4], the class forbidding $P_k$ and $\overline{P_k}$ has the strong Erdős–Hajnal property.