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 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$. Since neither outcome holds, $k>5$ and $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$.

Suppose neither $G[N]$ nor $G[M]$ is perfect. First they cannot both contain odd holes. Indeed, let $H_N\subseteq G[N]$ and $H_M\subseteq G[M]$ be odd holes of lengths $n$ and $m$. Every vertex of $H_M$ is nonadjacent to $u$, while $u$ is complete to $H_N$, so [L1] gives each vertex of $H_M$ at least $n-2$ neighbors in $H_N$. Thus there are at least $m(n-2)$ cross edges. On the other hand every vertex of $H_N$ is adjacent to $u$, while $u$ is anticomplete to $H_M$, so [L2] gives each vertex of $H_N$ at least $(m+1)\mathrm{/}2$ nonneighbors in $H_M$. Hence there are at least $n(m+1)\mathrm{/}2$ cross nonedges. Since there are only $mn$ cross pairs altogether, we obtain $m(n-2)+n(m+1)\mathrm{/}2\le mn$, equivalently $mn-4m+n\le 0$, impossible because $m,n\ge 5$ make the left-hand side at least $m+5>0$.

By [L4], the same argument in $\bar{G}$ shows that $G[N]$ and $G[M]$ cannot both contain odd antiholes. If $G[N]$ contained an odd hole, then step 1.1 would force $G[M]$ to contain no odd hole, so [L3] would give an odd antihole $H_M$ in $G[M]$. Because a $5$-antihole is also a $5$-hole, step 1.1 excludes the case $\mathrm{\mid }{H}_M\mathrm{\mid }=5$, and the same complement argument excludes $\mathrm{\mid }{H}_N\mathrm{\mid }=5$; hence both have length at least $7$. Now every vertex of $H_M$ is nonadjacent to $u$, so [L1] applied to the odd hole $H_N$ with complete outside vertex $u$ makes each vertex of $H_M$ complete to $H_N$. Applying the same lemma in $\bar{G}$ reverses the roles of hole and antihole and shows that each vertex of $H_N$ is anticomplete to $H_M$, contradiction. Therefore $G[N]$ has no odd hole, and by [L3] it must contain an odd antihole. Symmetrically, $G[M]$ contains an odd hole.

Take the odd antihole $H_N\subseteq G[N]$ and the odd hole $H_M\subseteq G[M]$ from step 2.1, with lengths $n$ and $m$. By [L2], each vertex of $H_N$ has at least $(m+1)\mathrm{/}2$ nonneighbors in $H_M$. Applying [L2] in the complement graph, where $H_N$ becomes an odd hole and $u$ is anticomplete to it, shows that each vertex of $H_M$ has at least $(n+1)\mathrm{/}2$ neighbors in $H_N$. Hence the number of cross nonedges is at least $n(m+1)\mathrm{/}2$ and the number of cross edges is at least $m(n+1)\mathrm{/}2$. Their sum is at least $(2mn+m+n)\mathrm{/}2>mn$, impossible. This contradiction proves that at least one of $G[N]$ and $G[M]$ is perfect.

We argue by induction on $\mathrm{\mid }V(G)\mathrm{\mid }$. Let $g$ be a good function on $G$. If $\mathrm{\mid }V(G)\mathrm{\mid }\le 1$, then ${\sum }_{v}g(v{)}^2\le 1$ because every one-vertex graph is perfect and therefore the good-function condition already gives $g(v)\le 1$. Assume now $\mathrm{\mid }V(G)\mathrm{\mid }\ge 2$, and choose $u\in V(G)$ with $g(u)$ maximal. Since every two-vertex induced subgraph is perfect, the good-function inequality implies $g(u)+g(v)\le 1$ for every $v\mathrm{\ne }u$, so if $g(u)=1$ then all other weights are $0$ and the desired inequality is immediate. Thus we may assume $g(u)<1$. By [L1], [L2], and [L3], after replacing $G$ by its complement if necessary we may assume that $G[N(u)]$ is perfect; this replacement preserves basicness, good functions, and the two-narrow inequality. Put $N=N(u)$ and $M=V(G)\setminus N[u]$. Any composite witness inside $G[M]$ would also be a composite witness inside $G$, so $G[M]$ is basic; by induction it is two-narrow.

For every perfect induced subgraph $P$ of $G[M]$, the graph $G[P\cup \{u\}]$ is perfect because $u$ is anticomplete to $P$ and adjoining an isolated vertex preserves the equalities $\chi =\omega$ on every induced subgraph. Hence the function $f(v)=g(v)\mathrm{/}(1-g(u))$ on $M$ is good on $G[M]$, so induction and [F1] give ${\sum }_{v\in M}g(v{)}^2\le (1-g(u){)}^2$. Also $G[N\cup \{u\}]$ is perfect because $u$ is complete to $N$ and adjoining a universal vertex raises both $\chi$ and $\omega$ by $1$. Thus the good-function inequality gives ${\sum }_{v\in N}g(v)\le 1-g(u)$. Since $g(u)$ is maximal, $g(v{)}^2\le g(u)g(v)$ for every $v\in N$, and therefore ${\sum }_{v\in N}g(v{)}^2\le g(u)(1-g(u))$.

Combining the contributions of $u$, $M$, and $N$ gives ${\sum }_{v\in V(G)}g(v{)}^2\le g(u{)}^2+(1-g(u){)}^2+g(u)(1-g(u))=1-g(u)+g(u{)}^2\le 1$. Since $g$ was an arbitrary good function, [F1] shows that $G$ is two-narrow.

Let $g$ be a good function on $G$. Let ${\mathcal{P}}_2$ be the family of perfect induced subgraphs of $H_2$, and let $K={\max }_{P\in {\mathcal{P}}_2}{\sum }_{x\in V(P)}g(x)$. If $K=0$, then every one-vertex induced subgraph of $H_2$ has weight $0$, so $g$ vanishes on $V(H_2)$. Choose any vertex $x\in V(H_2)$, define $g_1$ on $H_1$ by copying $g$ outside $v$ and setting $g_1(v)=0$, and note from [F2] that every perfect induced subgraph of $H_1$ corresponds either to the same perfect induced subgraph of $G$ or to one obtained by replacing $v$ with $x$. Hence $g_1$ is good on $H_1$, so [F1] gives ${\sum }_{y\in V(H_1)}{g}_1(y{)}^{\alpha }\le 1$. Because $g$ vanishes on $H_2$, this is exactly ${\sum }_{z\in V(G)}g(z{)}^{\alpha }\le 1$.

Assume now that $K>0$. Define $g_1$ on $H_1$ by copying $g$ outside $v$ and setting $g_1(v)=K$. If $Q$ is a perfect induced subgraph of $H_1$ not containing $v$, then it appears unchanged in $G$ and has total $g_1$-weight at most $1$. If $v\in V(Q)$, choose $P\in {\mathcal{P}}_2$ with ${\sum }_{x\in V(P)}g(x)=K$; then [L1] makes the substitution $Q[v\to P]$ a perfect induced subgraph of $G$, so ${\sum }_{y\in V(Q)}{g}_1(y)={\sum }_{y\in V(Q)\setminus \{v\}}g(y)+K={\sum }_{z\in V(Q[v\to P])}g(z)\le 1$. Thus $g_1$ is good on $H_1$. Likewise $g_2:=g\mathrm{/}K$ is good on $H_2$ by the definition of $K$. Applying [F1] to $g_1$ and $g_2$ gives ${\sum }_{y\in V(H_1)\setminus \{v\}}g(y{)}^{\alpha }+K^{\alpha }\le 1$ and ${\sum }_{x\in V(H_2)}g(x{)}^{\alpha }\le K^{\alpha }$.

In the case $K>0$, step 1.2 yields ${\sum }_{z\in V(G)}g(z{)}^{\alpha }={\sum }_{y\in V(H_1)\setminus \{v\}}g(y{)}^{\alpha }+{\sum }_{x\in V(H_2)}g(x{)}^{\alpha }\le 1$. Together with step 1.1, this proves that every good function on $G$ has $\alpha$-power sum at most $1$. Therefore [F1] shows that $G$ is $\alpha$-narrow.