Small-Graph Erdős-Hajnal Consequences

By [L1], every nonempty $P_4$-free graph $G$ satisfies $\mathrm{hom}(G)\ge \sqrt{\mathrm{\mid }V(G)\mathrm{\mid }}=\mathrm{\mid }V(G){\mathrm{\mid }}^{1\mathrm{/}2}$, so the class of $P_4$-free graphs has the positive exponent $1\mathrm{/}2$.

By [L2], the existence of that positive exponent is exactly the statement that $P_4$ has the Erdős-Hajnal property.

[assume-case small] If $\mathrm{\mid }V(H)\mathrm{\mid }\le 3$, then [L1] already gives the Erdős-Hajnal property for $H$.

[assume-case four] Assume $\mathrm{\mid }V(H)\mathrm{\mid }=4$. We distinguish whether $H$ is prime.

[assume-case prime] Suppose that $H$ is prime. Then [L3] gives an induced $P_4$ in $H$, and [F1] forces $H\cong P_4$. Therefore $H$ has the Erdős-Hajnal property by [L2].

[assume-case nonprime] Suppose that $H$ is not prime. Since $\mathrm{\mid }V(H)\mathrm{\mid }=4\ge 2$, [L4] yields a substitution representation $H\cong H_1[v\to H_2]$ with $\mathrm{\mid }V(H_1)\mathrm{\mid },\mathrm{\mid }V(H_2)\mathrm{\mid }\ge 2$. By [F2], both factors have at most three vertices, so [L1] gives the Erdős-Hajnal property for $H_1$ and $H_2$. Applying [L5], the substitution $H$ also has the Erdős-Hajnal property.

The cases in steps 1.1, 2.1, and 2.2 exhaust all graphs with at most four vertices. Hence every such graph has the Erdős-Hajnal property.

By [L1], the hereditary class of bull-free graphs has the positive exponent $1\mathrm{/}4$.

By [L2], that is exactly the statement that the bull graph has the Erdős-Hajnal property.

[assume-case forward] Assume first that $G$ is prime. By [L1], there is an induced path $p_1{p}_2{p}_3{p}_4$ in $G$. Let $x$ be the fifth vertex. We classify the neighbourhood $N_G(x)\cap \{p_1,p_2,p_3,p_4\}$.

[assume-case reverse] Conversely, each of the listed graphs is prime. For $P_5$ on vertices $1,2,3,4,5$ in path order, every nontrivial proper subset is split by an outside vertex: the pairs $\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{1,3\},\{1,4\},\{1,5\},\{2,4\},\{2,5\},\{3,5\}$ are split respectively by $3,1,2,3,4,3,2,1,4,2$, and the triples $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\}$ are split respectively by $4,3,3,2,4,3,1,1,3,2$; every four-vertex subset is split by the omitted vertex. For $C_5$, by cyclic symmetry, adjacent pairs are split by a neighbour of exactly one of them, nonadjacent pairs are split by their common neighbour, consecutive triples are split by the next cycle vertex, the other triple type is split by the middle omitted vertex, and a four-vertex subset is split by the omitted vertex. For the bull, writing the triangle as $a,b,c$ with leaves $y$ at $a$ and $z$ at $b$, every nontrivial proper subset is again split by an outside vertex: for instance $\{a,y\}$ by $b$, $\{b,y\}$ by $z$, $\{a,b\}$ by $y$, $\{c,y\}$ by $b$, $\{a,b,c\}$ by $y$, $\{a,b,y\}$ by $c$, and $\{a,y,z\}$ by $b$; the remaining cases follow by the automorphism swapping $(a,y)$ with $(b,z)$ or by the omitted vertex when the subset has size four. Thus $P_5$, $C_5$, and the bull have no nontrivial modules, so [L2] makes them prime; then [F1] gives the same for $\overline{P_5}$.

If $x$ has no neighbours on the path, then $x$ is isolated, so the four path vertices form a nontrivial module. If $x$ has all four path vertices as neighbours, then $x$ is isolated in the complement, and [F1] again gives a nontrivial module. Both cases contradict [L2].

If $x$ has exactly one neighbour, then either that neighbour is an endpoint or an internal path vertex. In the endpoint case, say $N_G(x)=\{p_1\}$, the order $x,p_1,p_2,p_3,p_4$ is a $P_5$. In the internal case, say $N_G(x)=\{p_2\}$, the set $\{p_1,x\}$ is a nontrivial module, since every other vertex is complete or anticomplete to that pair. Thus the only prime one-neighbour case is $P_5$.

If $x$ has exactly two neighbours, there are four patterns up to reversing the path: $\{p_1,p_2\}$, $\{p_1,p_3\}$, $\{p_1,p_4\}$, and $\{p_2,p_3\}$. For $\{p_1,p_2\}$ the set $\{p_1,x\}$ is a module; for $\{p_1,p_3\}$ the set $\{p_2,x\}$ is a module; for $\{p_1,p_4\}$ the cycle $x,p_1,p_2,p_3,p_4,x$ is a $C_5$; and for $\{p_2,p_3\}$ the vertices $p_1,p_2,p_3,x,p_4$ form a bull, with triangle $p_2{p}_{3}x$ and leaves $p_1,p_4$. Hence the only prime two-neighbour cases are $C_5$ and the bull.

If $x$ has exactly three neighbours, then exactly one path vertex is a non-neighbour. When that non-neighbour is an endpoint, say $p_1$, the set $\{p_3,x\}$ is a nontrivial module. When the unique non-neighbour is internal, say $p_3$, the order $p_2,p_4,p_1,p_3,x$ is an induced $\overline{P_5}$ by [L3]. Therefore the only prime three-neighbour case is $\overline{P_5}$.

Steps 2.1 through 2.4 exhaust all neighbourhood sizes of $x$, so every prime five-vertex graph is isomorphic to the bull, $C_5$, $P_5$, or $\overline{P_5}$.

Step 3.1 proves the forward direction and step 1.2 proves the reverse direction, so the stated equivalence holds.

[assume-case small] If $\mathrm{\mid }V(H)\mathrm{\mid }\le 4$, then [L1] gives the result.

[assume-case five] Assume $\mathrm{\mid }V(H)\mathrm{\mid }=5$. We distinguish whether $H$ is prime.

[assume-case prime] If $H$ is prime, then [L3] shows that $H$ is isomorphic to one of the four graphs listed in [L2]. Therefore $H$ has the Erdős-Hajnal property.

[assume-case nonprime] If $H$ is not prime, then [L4] gives a substitution representation $H\cong H_1[v\to H_2]$ with $\mathrm{\mid }V(H_1)\mathrm{\mid },\mathrm{\mid }V(H_2)\mathrm{\mid }\ge 2$. By [F1] both factors have at most four vertices, so [L1] gives the Erdős-Hajnal property for $H_1$ and $H_2$. Applying [L5], the graph $H$ also has the Erdős-Hajnal property.

The cases in steps 1.1, 2.1, and 2.2 exhaust all graphs with at most five vertices. Hence every such graph has the Erdős-Hajnal property.

By [L1] and the direction $(1)\Rightarrow (3)$ in [L2], the singleton family consisting only of the bull graph is viral.

Let $L$ be the left six-vertex prime $\mathcal{H}$-graph. By [F1], if we delete ${\mathrm{\ell }}_1$ from one copy of $L$ and ${\mathrm{\ell }}_2$ from another, both modified singleton families are the viral family $\{\text{bull}\}$. Applying [L3] with the same graph $L$ in both leaf-deletion slots shows that the singleton family $\{L\}$ is viral. Using the direction $(3)\Rightarrow (1)$ in [L2], we conclude that $L$ has the Erdős-Hajnal property.

Let $R$ be the right six-vertex prime $\mathcal{H}$-graph. By [F2], we have $R=\bar{L}$, so [L4] transfers the Erdős-Hajnal property from $L$ to $R$.

Therefore both six-vertex prime $\mathcal{H}$-graphs have the Erdős-Hajnal property.

By [L1], the two-vertex graph $K_2$ has the Erdős-Hajnal property, and by [L2] so does $C_5$.

By [F1] and [L3], the graph $H_0$ is obtained by substituting $C_5$ for one vertex of $K_2$. Therefore [L4] applies to the two graphs of step 1.1 and gives the Erdős-Hajnal property for $H_0$.