Bull-Free Graphs and the Erdős-Hajnal Property — Examples

Define $\phi$ by $\phi (x_1)=y$, $\phi (x_2)=z$, $\phi (x_3)=x_3$, $\phi (y)=x_2$, and $\phi (z)=x_1$. Using [F1] and [F2], one checks that the five complement-edges are exactly the images under $\phi$ of the five bull edges.

Thus $\phi$ is an isomorphism from the bull to its complement, so the bull is self-complementary.

The graph $C_5$ is triangle-free by [F2], whereas every bull contains a triangle by [F1]. So $C_5$ contains no induced bull and is bull-free.

In $C_5$, the largest clique has size $2$, while a proper vertex colouring needs $3$ colours. Hence $\omega (C_5)=2<3=\chi (C_5)$, so [F3] shows that $C_5$ is not perfect.

Therefore $C_5$ is a bull-free graph that is not perfect, refuting the claim.

Every induced subgraph of $K_4$ is complete, while the bull has nonadjacent vertex pairs. So $K_4$ has no induced bull and is bull-free by [F1].

Let $M=\{v_1,v_2\}\subseteq V(K_4)$. Every vertex outside $M$ is adjacent to both $v_1$ and $v_2$ by [F3], so it is complete to $M$. Thus [F2] makes $M$ a module. Since $\mathrm{\mid }M\mathrm{\mid }=2$ and $M\mathrm{\ne }V(K_4)$, it is nontrivial.

By [L2], the graph $C_5$ is bull-free. The bull-free theorem [L1] therefore gives the two-narrow half of the example.

Define $g(v)=1\mathrm{/}4$ for every vertex of $C_5$. Every proper induced subgraph of $C_5$ is a forest on at most four vertices, hence is bipartite and has clique number at most $2$; the same is true for each of its induced subgraphs, so every proper induced subgraph of $C_5$ is perfect. Since [L2] says the whole $C_5$ is not perfect, the perfect induced subgraphs of $C_5$ are exactly the proper ones, and each has at most four vertices. Therefore [F2] makes $g$ a good function, because its total on any perfect induced subgraph is at most $4\cdot (1\mathrm{/}4)=1$. But ${\sum }_{v\in V(C_5)}g(v)=5\mathrm{/}4>1$, so [F1] shows that $C_5$ is not one-narrow.

Thus $C_5$ is two-narrow by step 1.1 but not one-narrow by step 1.2.

By [L1], the graph $C_5$ is already a counterexample to the claim.

Therefore the claim is false.

The example [L1] furnishes a graph $C_5$ that satisfies the hypothesis of the false claim but not its conclusion.

Therefore the implication is false.