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.

Deleting any vertex of $C_5$ leaves a four-vertex path. Every induced subgraph of that path is a disjoint union of paths. If it has an edge, alternating colours on each path give chromatic number at most $2$, and the edge gives clique number at least $2$, so both numbers are $2$; if it is nonempty and has no edge, both are $1$; and if it is empty, both are $0$. Thus every vertex deletion is perfect by [F3]. Since $C_5$ has five vertices, [L1] proves that $C_5$ is two-narrow.

Define $g(v)=1\mathrm{/}4$ for every vertex of $C_5$. Every proper induced subgraph lies in some vertex deletion, so it is perfect by step 1.1. Since [L2] says the whole $C_5$ is not perfect, every perfect induced subgraph is proper and has at most four vertices. Thus [F2] makes $g$ a good function: its total on each 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 2.1.

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.