Every $P_3$-free graph $G$ satisfies $\mathrm{hom}(G)\ge \sqrt{\mathrm{\mid }V(G)\mathrm{\mid }}$

If $G$ is null, then $\mathrm{hom}(G)=0=\sqrt{0}$ by [L1] and [L8]. Assume henceforth that $G$ is nonempty.

Every connected component of $G$ is a clique: otherwise two nonadjacent vertices in one component have a shortest path $v_0,\dots ,v_{\mathrm{\ell }}$ with $\mathrm{\ell }\ge 2$; the vertices $v_0,v_1,v_2$ are distinct, the consecutive pairs are edges, and $v_0{v}_2$ is not an edge because it would shorten the path, so they induce $P_3$, contrary to [L3].

Let $r\ge 1$ be the number of connected components of $G$. Choosing one vertex from each of these finitely many nonempty components gives a stable set, since an edge would put its endpoints in one component; hence $\alpha (G)\ge r$.

Let the component orders be $c_1,\dots ,c_r$. By [L6], $r\ge 1$, each $c_i\ge 1$, and $\mathrm{\mid }V(G)\mathrm{\mid }={\sum }_i{c}_i$; step 1.2 gives $\omega (G)\ge {\max }_i{c}_i$.

Therefore $\mathrm{\mid }V(G)\mathrm{\mid }={\sum }_i{c}_i\le r{\max }_i{c}_i\le \alpha (G)\omega (G)\le \mathrm{hom}(G{)}^2$.

Both sides are nonnegative, so [L8] and step 3.1 yield $\mathrm{hom}(G)\ge \sqrt{\mathrm{\mid }V(G)\mathrm{\mid }}=\mathrm{\mid }V(G){\mathrm{\mid }}^{1\mathrm{/}2}$. Together with [L2] and [L3], this makes $1\mathrm{/}2$ an Erdős–Hajnal constant for the $P_3$-free class.