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

By [F1] and [F2], the complement of the bull is again a bull: the bijection $x_1\mapsto y$, $x_2\mapsto z$, $x_3\mapsto x_3$, $y\mapsto x_2$, $z\mapsto x_1$ sends nonedges of the bull to edges of the bull.

If $G$ contains an induced bull on a vertex set $S$, then $\bar{G}[S]$ is the complement of that bull, hence another bull by step 1.1. The same argument with $G$ and $\bar{G}$ interchanged proves the converse implication.

Therefore $G$ has an induced bull exactly when $\bar{G}$ does, so [F3] gives the equivalence of bull-freeness.

Let $g$ be any good function on $G$. Choose a vertex $v_0$ with minimum weight $m=g(v_0)$, and put $A={\sum }_{v\mathrm{\ne }{v}_0}g(v)$.

Since $G-v_0$ is perfect, [F1] gives $A\le 1$. The other $n-1$ weights are each at least $m\ge 0$, so $A\ge (n-1)m$. For any $u\mathrm{\ne }{v}_0$, the remaining $n-2$ weights in $A$ are at least $m$, hence $g(u)\le A-(n-2)m$.

Consequently ${\sum }_{v\in V(G)}g(v{)}^2\le m^2+(A-(n-2)m)A=A^2-m((n-2)A-m)\le A^2\le 1$. Indeed, $(n-2)A\ge (n-2)(n-1)m\ge m$ because $n\ge 3$ and $m\ge 0$.

This holds for every good $g$, so $G$ is two-narrow by [F2].

Let $g$ be a good function on $G$. By [F3], the graph $G$ itself is a perfect induced subgraph of $G$, so [F2] gives ${\sum }_{v\in V(G)}g(v)\le 1$.

Since every good function has total weight at most $1$, [F1] shows that $G$ is one-narrow.

Let $K$ be the maximum order of a perfect induced subgraph of $G$. Since $G$ is nonempty, every one-vertex induced subgraph is perfect, so $K\ge 1$. Define $g(v)=1\mathrm{/}K$ for every $v\in V(G)$. If $P$ is a perfect induced subgraph of $G$, then $\mathrm{\mid }V(P)\mathrm{\mid }\le K$, so ${\sum }_{v\in V(P)}g(v)=\mathrm{\mid }V(P)\mathrm{\mid }\mathrm{/}K\le 1$. Thus $g$ is good by [F2].

If $G$ is $\alpha$-narrow, [F1] applied to the good function of step 1.1 yields $\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{K}^{\alpha }={\sum }_{v\in V(G)}g(v{)}^{\alpha }\le 1$. Therefore $K^{\alpha }\ge \mathrm{\mid }V(G)\mathrm{\mid }$. Since $K\ge 1$ and $\mathrm{\mid }V(G)\mathrm{\mid }\ge 1$, both sides are positive, so applying [L1] with exponent $1\mathrm{/}\alpha >0$ and then using [L2] gives $K=(K^{\alpha }{)}^{1\mathrm{/}\alpha }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{1\mathrm{/}\alpha }$.

By definition of $K$, there is a perfect induced subgraph of order $K$, and step 2.1 gives $K\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{1\mathrm{/}\alpha }$.

Let $P$ be the perfect induced subgraph given by [L1]. Applying [L2] to $P$ and then using [F1] gives $\mathrm{\mid }V(P)\mathrm{\mid }\le \alpha (P)\omega (P)$. Hence either $\alpha (P)\ge \mathrm{\mid }V(P){\mathrm{\mid }}^{1\mathrm{/}2}$ or $\omega (P)\ge \mathrm{\mid }V(P){\mathrm{\mid }}^{1\mathrm{/}2}$. So $P$, and therefore $G$, has a stable set or clique of size at least $\mathrm{\mid }V(P){\mathrm{\mid }}^{1\mathrm{/}2}$.

Since $\mathrm{\mid }V(P)\mathrm{\mid }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{1\mathrm{/}\alpha }$, step 1.1 yields a clique or stable set of size at least $\mathrm{\mid }V(G){\mathrm{\mid }}^{1\mathrm{/}(2\alpha )}$ by [F3].

First claim: if $x\in V(G)\setminus S$ is neither complete nor anticomplete to $S$, then either $c$ is adjacent to $a$ and $x$ is adjacent to $c$, or $c$ is nonadjacent to $a$ and $x$ is nonadjacent to $a$. Indeed, let $S_1$ be the neighbors of $x$ in $S$ and $S_2=S\setminus S_1$; both are nonempty. By [F1], either there are $u,v\in S_1$ and $w\in S_2$ with $u$-$v$-$w$ an induced path, or there are $u\in S_1$ and $v,w\in S_2$ with $uw\in E(G)$ while $uv,vw\mathrm{\notin }E(G)$. In the first case bull-freeness rules out both $x$-$a$ and $\overline{xc}$ simultaneously, because otherwise $\{a,x,u,v,w\}$ and then $\{x,v,w,c,a\}$ would be bulls. In the second case bull-freeness similarly rules out both $\overline{xc}$ and $x$-$a$, because otherwise $\{x,u,w,c,v\}$ and then $\{a,x,u,c,v\}$ would be bulls.

Let $C$ be the set of vertices complete to $S$, let $A$ be the set of vertices anticomplete to $S$, and let $X=V(G)\setminus (S\cup C\cup A)$. Either every vertex of $C$ has a neighbor in $A$, or every vertex of $A$ has a nonneighbor in $C$: otherwise a vertex of $C$ anticomplete to $A$ and a vertex of $A$ complete to $C$ would contradict each other. Replacing $G$ by $\bar{G}$ if necessary preserves bull-freeness, splitness, and modules by [L1], [F1], and [F2], so assume that every vertex of $C$ has a neighbor in $A$. Step 1.1 then makes $C$ complete to $X$. Let $A^{\mathrm{\prime }}$ be the set of vertices of $A$ lying on an induced path $x$-$a_1$-$\cdots$-$a_k$ with $x\in X$ and all $a_i\in A$. We prove by induction on $k$ that $a_k$ is complete to $C$. For $k=1$, if $c^{\mathrm{\prime }}{a}_1$ were a nonedge for some $c^{\mathrm{\prime }}\in C$, step 1.1 applied to $x,c^{\mathrm{\prime }},a_1$ would force $x{a}_1$ to be a nonedge, a contradiction. For $k>1$, put $a_0=x$ and assume the result through $a_{k-1}$. Choose $s\in S$ nonadjacent to $a_{k-2}$ when $k=2$, which is possible because $x$ is mixed on $S$; for $k>2$ any $s\in S$ works because $a_{k-2}\in A$. If some $c^{\mathrm{\prime }}\in C$ were nonadjacent to $a_k$, then $\{s,c^{\mathrm{\prime }},a_{k-2},a_{k-1},a_k\}$ would be a bull: $c^{\mathrm{\prime }},a_{k-2},a_{k-1}$ form its triangle, while $s$ and $a_k$ are pendant at $c^{\mathrm{\prime }}$ and $a_{k-1}$. Hence $A^{\mathrm{\prime }}$ is complete to $C$.

Put $Z=S\cup X\cup A^{\mathrm{\prime }}$. Every vertex of $A\setminus A^{\mathrm{\prime }}$ is anticomplete to $Z$: it is anticomplete to $S$ by definition, and any path from it to $X\cup A^{\mathrm{\prime }}$ through $A$ has a shortest, hence induced, subpath that would put it in $A^{\mathrm{\prime }}$. Every vertex of $C$ is complete to $Z$ by step 2.1 and the definition of $C$. Thus every outside vertex is complete or anticomplete to $Z$, so $Z$ is a module by [F2]. The set $Z$ is nontrivial because $S\subseteq Z$ and $\mathrm{\mid }S\mathrm{\mid }>1$, while $c\in C\setminus Z$, so $Z\mathrm{\ne }V(G)$.

By [F1] and [L2], after passing to the complement if needed we may assume that $A$ is an odd hole with vertices $h_1,\dots ,h_k$ in cyclic order, together with a vertex $c$ complete to $V(A)$ and a vertex $a$ anticomplete to $V(A)$. To apply [L1], it is enough to show that $V(A)$ is split.

Let $x\in V(G)\setminus V(A)$ be neither complete nor anticomplete to $V(A)$. By cyclic symmetry, assume $x$ is adjacent to $h_1$ and nonadjacent to $h_2$. If $x$ is adjacent to $h_k$, then the path $h_k$-$h_1$-$h_2$ gives the first split alternative from [F2]. So assume $x$ is nonadjacent to $h_k$. If $x$ is also nonadjacent to $h_{k-1}$, then $h_1{h}_2\in E(G)$ while $h_1{h}_{k-1},h_{k-1}{h}_2\mathrm{\notin }E(G)$, so the triple $(h_1,h_{k-1},h_2)$ gives the second split alternative. Otherwise $x$ is adjacent to $h_{k-1}$, and then $h_{k-1}{h}_k\in E(G)$ while $h_{k-1}{h}_2,h_2{h}_k\mathrm{\notin }E(G)$, so the triple $(h_{k-1},h_2,h_k)$ gives the second split alternative. Hence every mixed outside vertex satisfies [F2], so $V(A)$ is split.

Step 1.2 shows that the odd hole $A$ is a split set, and step 1.1 supplies a complete and an anticomplete outside vertex for it. Therefore [L1] gives a nontrivial module in $G$.

If $G$ were composite, then the composite-case theorem [L1] would supply a nontrivial module of $G$. This contradicts [F2], so $G$ is not composite.

Since $G$ is bull-free and not composite, [F1] says that $G$ is basic.

Because $G$ is basic, $u$ cannot be anticomplete to $V(H)$: otherwise the odd hole $H$ would have the complete outside vertex $c$ and the anticomplete outside vertex $u$, making $G$ composite and contradicting [F1]. Assume neither outcome of the Statement holds. By cyclic symmetry choose $h_1$ adjacent to $u$. Suppose that $u$ is adjacent to $h_2$. Since $\{h_k,h_1,u,h_2,h_3\}$ is not a bull, $u$ is adjacent to at least one of $h_k,h_3$; after reversing and shifting the cyclic labels in the second case, we may assume that $u$ is adjacent to $h_k$. If $k=5$, the three distinct neighbors $h_1,h_2,h_k$ give outcome 2, contrary to our assumption. Thus $k>5$, and outcome 1 failing means $u$ is not complete to $H$. Since $\{u,h_2,h_3,c,h_{k-1}\}$ is not a bull, $u$ is adjacent to at least one of $h_3,h_{k-1}$; reflecting the cyclic labels through $h_1$ if necessary, we may assume that $u$ is adjacent to $h_3$. Let $i>3$ be minimal with $u$ nonadjacent to $h_i$. Minimality makes $u$ adjacent to $h_{i-2},h_{i-1}$, while $u$ is adjacent to $h_k$. If $i\mathrm{\ne }k-1$, then $\{h_i,h_{i-1},h_{i-2},u,h_k\}$ is a bull, so $i=k-1\ge 5$. But then $\{h_i,h_{i-1},h_{i-2},u,h_1\}$ is a bull, a contradiction. Thus $u$ is not adjacent to $h_2$; applying the same argument to any putative consecutive pair shows that $u$ has no two consecutive neighbors on $H$.

Since $u$ is adjacent to $h_1$ but to no consecutive pair on $H$, the vertices $\{u,h_1,h_2,c,h_i\}$ with $4\le i\le k-1$ would induce a bull unless $u$ were adjacent to every such $h_i$. Reflecting the cycle through $h_1$ gives the same conclusion for $h_3,\dots ,h_{k-2}$. In particular $u$ is adjacent to both $h_3$ and $h_4$, a consecutive pair, contradicting step 1.1. Therefore our assumption that neither outcome holds was impossible.

One of the two stated outcomes must hold.

Because $G$ is basic, $u$ cannot be complete to $V(H)$: together with the anticomplete outside vertex $a$, that would make the odd hole $H$ a composite witness, contrary to [F1]. So $u$ has a nonneighbor on $H$. Suppose $u$ had two consecutive neighbors, say $h_1$ and $h_2$. Let $i$ be minimal with $u$ nonadjacent to $h_i$; then $i\ge 3$, and minimality gives $u$ adjacent to $h_{i-1}$ and $h_{i-2}$. Since $a$ is anticomplete to $H$, the five vertices $\{a,u,h_{i-2},h_{i-1},h_i\}$ induce a bull, contradicting bull-freeness. Therefore $u$ has no two consecutive neighbors on $H$.

On a cycle of length $k$, any vertex subset with no two consecutive vertices has size at most $\lfloor k\mathrm{/}2\rfloor$. Step 1.1 therefore bounds the number of neighbors of $u$ on $H$ by $\lfloor k\mathrm{/}2\rfloor$, so the number of nonneighbors is at least $k-\lfloor k\mathrm{/}2\rfloor =\lceil k\mathrm{/}2\rceil$.

Induct on $\mathrm{\mid }V(G)\mathrm{\mid }$. For $G=K_1$, its replication is $K_2$, whose induced subgraphs have equal chromatic and clique numbers. Assume the assertion for smaller perfect graphs. Every proper induced subgraph of $G^{\mathrm{\prime }}$ either contains at most one of $x,x^{\mathrm{\prime }}$ and is isomorphic to an induced subgraph of $G$, or contains both and is the replication of $x$ in a proper induced subgraph of $G$. It is perfect by [L3] or by the induction hypothesis, respectively. Thus it remains to show $\chi (G^{\mathrm{\prime }})=\omega (G^{\mathrm{\prime }})$.

Put $w=\omega (G)=\chi (G)$. Every clique of $G^{\mathrm{\prime }}$ contains at most the one additional vertex $x^{\mathrm{\prime }}$, so $\omega (G^{\mathrm{\prime }})$ is $w$ or $w+1$. If it is $w+1$, color $G$ with $w$ colors and give $x^{\mathrm{\prime }}$ a new color. Then $\chi (G^{\mathrm{\prime }})\le w+1=\omega (G^{\mathrm{\prime }})$, and the reverse inequality holds in every graph.

Suppose $\omega (G^{\mathrm{\prime }})=w$. No $w$-clique of $G$ contains $x$, since its union with $x^{\mathrm{\prime }}$ would be a $(w+1)$-clique of $G^{\mathrm{\prime }}$. Fix a proper $w$-coloring of $G$, and let $X$ be the color class of $x$. Every $w$-clique of $G$ meets $X$ exactly once by [L2], and that meeting vertex is not $x$. Hence the induced graph $H=G-(X\setminus \{x\})$ has no $w$-clique and $\omega (H)\le w-1$. Since $H$ is perfect by [L3], it admits a coloring with at most $w-1$ colors.

The remaining set $(X\setminus \{x\})\cup \{x^{\mathrm{\prime }}\}$ is stable in $G^{\mathrm{\prime }}$: $X$ was a color class, and $x^{\mathrm{\prime }}$ is adjacent outside $x$ only to neighbors of $x$, none of which lies in $X$. Give that set one new color, extending the coloring of $H$ to a $w$-coloring of $G^{\mathrm{\prime }}$. Thus $\chi (G^{\mathrm{\prime }})\le w=\omega (G^{\mathrm{\prime }})$; the opposite inequality is universal. With step 2.1, this proves $G^{\mathrm{\prime }}$ perfect by step 1.1. To replace $x$ by a clique of $k\ge 1$ true twins, replicate $x$ successively $k-1$ times; each step starts from a perfect graph and creates one further twin.

If $G$ is perfect, color each induced $H$ with $\omega (H)$ colors. Each color class is stable and has at most $\alpha (H)$ vertices, so $\mathrm{\mid }V(H)\mathrm{\mid }\le \alpha (H)\omega (H)$. This includes the empty graph, for which both sides are zero.

Conversely, assume the numerical inequality for every induced subgraph of $G$ and induct on $n=\mathrm{\mid }V(G)\mathrm{\mid }$. It passes to each proper induced subgraph, so those subgraphs are perfect by induction. The empty case is immediate. Suppose for contradiction that nonempty $G$ is not perfect. Put $a=\alpha (G)$, $w=\omega (G)$ and $d=aw+1$. Then $\chi (G)>w$, while the assumed inequality gives $n\le aw=d-1$.

If $U\subseteq V(G)$ is a nonempty stable set, then $G-U$ is a proper perfect induced subgraph. It must have a $w$-clique: otherwise $\chi (G-U)=\omega (G-U)\le w-1$, and coloring $U$ with one new color would give $\chi (G)\le w$, contrary to step 1.2. This also covers $G-U$ empty.

Fix a maximum stable set $A_0=\{u_1,\dots ,u_a\}$. For each $i$, choose an optimal $w$-coloring of $G-u_i$, possible by step 2.1 and perfection of that proper induced subgraph. Name its $w$ color classes $A_{(i-1)w+1},\dots ,A_{iw}$. Thus $A_0,A_1,\dots ,A_{aw}$ are $d=aw+1$ stable sets. By step 2.1, for each $j\in \{0,\dots ,aw\}$ fix a $w$-clique $K_j$ in $G-A_j$. All selections are from finite families.

Let $K$ be any $w$-clique of $G$. If $K\cap A_0=\mathrm{\varnothing }$, then for every $i$ it is a $w$-clique of $G-u_i$ and meets each of that graph's $w$ color classes exactly once. If $K\cap A_0=\{u_i\}$, then it meets $A_0$ once; in the $i$th coloring, its other $w-1$ vertices occupy exactly $w-1$ of the $w$ color classes, so it misses exactly one class in that block. For each other $u_h\in A_0$ it meets all $w$ classes of the $h$th coloring. A clique meets $A_0$ at most once. Therefore $K$ is disjoint from exactly one of $A_0,\dots ,A_{aw}$ and meets every other one in exactly one vertex. In particular, $\mathrm{\mid }{A}_i\cap K_j\mathrm{\mid }=0$ if $i=j$ and $1$ if $i\mathrm{\ne }j$.

Enumerate $V(G)=\{v_1,\dots ,v_n\}$. Let $A$ be the real $d\times n$ matrix whose $i$th row is the incidence vector of $A_i$, and let $B$ be the real $n\times d$ matrix whose $j$th column is the incidence vector of $K_j$. By step 4.1, $AB=J_d-I_d$: its diagonal entries are $0$ and all off-diagonal entries are $1$. This $d\times d$ matrix has independent columns. Indeed, if $(J_d-I_d)z=0$, put $s={\sum }_i{z}_i$. Each coordinate equation says $s-z_i=0$, so all $z_i=s$; then $s=ds$, and $d\ge 2$ forces $s=0$ and $z=0$. Hence the $d$ columns of $B$ are independent: any linear relation among them would remain a relation after multiplying by $A$. But $d>n$ by step 1.2, contradicting [L3] for vectors of ${\mathbb{R}}^n$.

The contradiction discharges step 1.2, proving the numerical criterion. If $G$ is perfect, step 1.1 gives the inequality for every induced $H$. For each induced subgraph $\bar{H}$ of $\bar{G}$, [L2] gives $\mathrm{\mid }V(\bar{H})\mathrm{\mid }=\mathrm{\mid }V(H)\mathrm{\mid }$, $\alpha (\bar{H})=\omega (H)$, and $\omega (\bar{H})=\alpha (H)$; so the same inequality holds in $\bar{G}$. The criterion makes $\bar{G}$ perfect. Applying that direction to $\bar{G}$ proves the converse, because $\overline{\stackrel{‾}{G}}=G$.