Cographs, Perfect Patterns and Pure Pairs

We argue by induction on the recursive definition of cographs. If $G$ is the null graph or a one-vertex graph, then $G[X]$ is again the null graph or a one-vertex graph, so it is a cograph by [L1].

Assume now that $G$ is nontrivial, and that the claim is already known for the two smaller cographs in the last construction step of $G$. By [L1], there exist vertex-disjoint smaller cographs $G_1$ and $G_2$ such that $G$ is either their disjoint union or their complete connection. Put $X_i:=X\cap V(G_i)$ for $i=1,2$. The induction hypothesis gives that $G_i[X_i]$ is a cograph for $i=1,2$.

If $G$ is the disjoint union of $G_1$ and $G_2$, then [L2] gives $G[X]=G_1[X_1]\bigsqcup G_2[X_2]$, a disjoint union of cographs. If $G$ is $G_1\mathrm{\nabla }{G}_2$, then [L2] gives $G[X]=G_1[X_1]\mathrm{\nabla }{G}_2[X_2]$, a complete connection of cographs. In either case the recursive definition shows that $G[X]$ is a cograph.

Steps 1.1 and 2.1 complete the induction, so every induced subgraph of a cograph is a cograph.

By [L1], there exist nonempty smaller cographs $G_1$ and $G_2$ such that $G$ is either the disjoint union of $G_1$ and $G_2$, or the complete connection $G_1\mathrm{\nabla }{G}_2$.

In the disjoint-union case, [L2] immediately shows that $G$ is disconnected.

In the complete-connection case, [L3] shows that $\bar{G}=\overline{G_1}\bigsqcup \overline{G_2}$. Both sides are nonempty because $G_1$ and $G_2$ are nonempty, so $\bar{G}$ is disconnected by [L2].

Therefore one of the two stated alternatives always holds: either $G$ is disconnected, or $\bar{G}$ is disconnected.

Suppose first that $G$ is a cograph. If $G$ had an induced copy of $P_4$ on some vertex set $X$, then [L1] would make $G[X]$ a cograph. But $G[X]$ is isomorphic to $P_4$, and [L3] shows that both $P_4$ and its complement are connected, contradicting [L2]. Therefore every cograph is $P_4$-free.

For the converse, we prove by induction on $n:=\mathrm{\mid }V(G)\mathrm{\mid }$ that every $P_4$-free graph on $n$ vertices is a cograph. If $n\le 1$, then $G$ is the null graph or a one-vertex graph, and the recursive definition makes it a cograph.

Assume now that $n\ge 2$ and that every smaller $P_4$-free graph is a cograph. Because $G$ is $P_4$-free, [L4] gives that $G$ is disconnected or $\bar{G}$ is disconnected.

If $G$ is disconnected, choose a connected component $C$ of $G$ and let $D:=V(G)\setminus C$. Then $C$ and $D$ are nonempty, [L5] makes them anticomplete, and [F2] makes both $G[C]$ and $G[D]$ smaller $P_4$-free graphs. By the induction hypothesis they are cographs, so $G$ is their disjoint union and hence a cograph.

If $\bar{G}$ is disconnected, choose an anticomponent $C$ of $G$ and let $D:=V(G)\setminus C$. Again $C$ and $D$ are nonempty, [L5] makes them complete to one another, and [F2] makes $G[C]$ and $G[D]$ smaller $P_4$-free graphs. By the induction hypothesis they are cographs, so $G$ is their complete connection and hence a cograph.

Steps 3.1 and 3.2 close the induction, proving that every $P_4$-free graph is a cograph. Together with step 1.1, this proves the equivalence.

Suppose for contradiction that $G$ contains no induced $P_4$. Then [L2] shows that $G$ is a cograph. Since $\mathrm{\mid }V(G)\mathrm{\mid }\ge 4$, the graph is nontrivial, so [L3] gives that $G$ is disconnected or $\bar{G}$ is disconnected.

If $G$ is disconnected, its connected components form a partition of $V(G)$ into at least two nonempty parts. By [F1], choose a proper union $M$ of component vertex sets with $2\le \mathrm{\mid }M\mathrm{\mid }\le \mathrm{\mid }V(G)\mathrm{\mid }-1$. Then [L4] makes $M$ a module of $G$, and the cardinality bounds say that it is nontrivial. This contradicts [L1].

If $\bar{G}$ is disconnected, then the anticomponents of $G$ form a partition of $V(G)$ into at least two nonempty parts. Again [F1] gives a proper union $M$ of anticomponent vertex sets with $2\le \mathrm{\mid }M\mathrm{\mid }\le \mathrm{\mid }V(G)\mathrm{\mid }-1$, and [L4] makes $M$ a nontrivial module of $G$, contradicting [L1].

Both alternatives from step 1.1 are impossible, so the assumption was false. Therefore $G$ contains an induced copy of $P_4$.

Let $X\subseteq V_G\cup V_H$, and write $X_G:=X\cap V_G$ and $X_H:=X\cap V_H$. Since $G$ and $H$ are perfect, [L1] gives $\chi (G[X_G])=\omega (G[X_G])$ and $\chi (H[X_H])=\omega (H[X_H])$.

By [L2], the induced subgraph of $G\bigsqcup H$ on $X$ is $G[X_G]\bigsqcup H[X_H]$. Applying [L3] to that disjoint union and then using step 1.1 yields $\chi ((G\bigsqcup H)[X])=\max \{\chi (G[X_G]),\chi (H[X_H])\}=\max \{\omega (G[X_G]),\omega (H[X_H])\}=\omega ((G\bigsqcup H)[X])\mathrm{.}$

Step 2.1 proves $\chi (K)=\omega (K)$ for every induced subgraph $K=(G\bigsqcup H)[X]$, so the disjoint union $G\bigsqcup H$ is perfect by [L1].

Let $X\subseteq V_G\cup V_H$, and write $X_G:=X\cap V_G$ and $X_H:=X\cap V_H$. Because $G$ and $H$ are perfect, [L1] gives $\chi (G[X_G])=\omega (G[X_G])$ and $\chi (H[X_H])=\omega (H[X_H])$.

By [L2], the induced subgraph of $G\mathrm{\nabla }H$ on $X$ is $G[X_G]\mathrm{\nabla }H[X_H]$. Applying [L3] to that complete connection and then using step 1.1 yields $\chi ((G\mathrm{\nabla }H)[X])=\chi (G[X_G])+\chi (H[X_H])=\omega (G[X_G])+\omega (H[X_H])=\omega ((G\mathrm{\nabla }H)[X])\mathrm{.}$

Step 2.1 proves $\chi (K)=\omega (K)$ for every induced subgraph $K=(G\mathrm{\nabla }H)[X]$, so $G\mathrm{\nabla }H$ is perfect by [L1].

We argue by induction on the recursive definition of cographs. If $G$ is the null graph or a one-vertex graph, then [F1] shows that $G$ is perfect.

Assume now that $G$ is nontrivial and that the claim is already known for the two smaller cographs in its final construction step. By [L1], there exist smaller cographs $G_1$ and $G_2$ such that $G$ is either $G_1\bigsqcup G_2$ or $G_1\mathrm{\nabla }{G}_2$. The induction hypothesis makes both $G_1$ and $G_2$ perfect.

In the disjoint-union case, [L2] shows that $G$ is perfect. In the complete-connection case, [L3] shows that $G$ is perfect.

Steps 1.1 and 2.1 close the induction. Therefore every cograph is perfect.

Combining [L1] and [L2] gives $\mathrm{\mid }V(G)\mathrm{\mid }\le \chi (G)\alpha (G)=\omega (G)\alpha (G)\mathrm{.}$

The right-hand side of step 1.1 is $\kappa (G)$ by [L3]. Therefore $\mathrm{\mid }V(G)\mathrm{\mid }\le \kappa (G)$.

Let $h:=\mathrm{hom}(G)=\max \{\alpha (G),\omega (G)\}$. Then $\alpha (G)\le h$ and $\omega (G)\le h$, so [L2] gives $\kappa (G)=\alpha (G)\omega (G)\le h^2\mathrm{.}$

Since $n=\mathrm{\mid }V(G)\mathrm{\mid }$, [L1] and step 1.1 yield $n\le h^2$. Therefore $h\ge \sqrt{n}$. If $h=\omega (G)$, $G$ has a clique of size at least $\sqrt{n}$; if $h=\alpha (G)$, it has a stable set of that size.

Hence every perfect graph on $n$ vertices has a clique or stable set of size at least $\sqrt{n}$.

Assume clause 1. By [L1], choose $\tau >0$ such that every nonempty $\mathcal{H}$-free graph $G$ satisfies $\mathrm{hom}(G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$. For such a graph, choose a homogeneous set $S$ with $\mathrm{\mid }S\mathrm{\mid }=\mathrm{hom}(G)$. Then [F1] shows that $G[S]$ is a cograph on at least $\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$ vertices. Hence clause 2 holds with the same exponent $\tau$.

Assume clause 2 with exponent $\tau >0$. Every cograph is perfect by [L2], so the same induced subgraph witnesses clause 3 with the same exponent.

Assume clause 3 with exponent $\tau >0$, and let $G$ be a nonempty $\mathcal{H}$-free graph. Choose an induced perfect subgraph $J$ of $G$ with $\mathrm{\mid }V(J)\mathrm{\mid }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$. By [L3], the graph $J$ has a clique or stable set of size at least $\mathrm{\mid }V(J){\mathrm{\mid }}^{1\mathrm{/}2}$. Since $\mathrm{\mid }V(J)\mathrm{\mid }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }>0$, [L5] gives $\mathrm{\mid }V(J){\mathrm{\mid }}^{1\mathrm{/}2}\ge (\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }{)}^{1\mathrm{/}2}=\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau \mathrm{/}2}$, where the equality is [L4]. Then [F2] turns that clique or stable set into one in $G$. Therefore clause 1 holds, with exponent $\tau \mathrm{/}2$.

For a nonempty graph $G$, [F3] gives $\mathrm{hom}(G)\le \kappa (G)\le \mathrm{hom}(G{)}^2$. Therefore clause 1 implies clause 4 with the same exponent. Conversely, if clause 4 holds with exponent $\tau$, then $\mathrm{hom}(G{)}^2\ge \kappa (G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }>0$, so [L5] gives $\mathrm{hom}(G)\ge (\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }{)}^{1\mathrm{/}2}=\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau \mathrm{/}2}$. Hence clause 4 implies clause 1.

The implications in steps 1.1, 1.2, and 1.3 prove $1\Rightarrow 2\Rightarrow 3\Rightarrow 1$.

Step 2.1 gives the forward implication chain from clause 1 to clause 3 and back, while step 1.4 proves the equivalence of clauses 1 and 4. Therefore all four formulations are equivalent.

Applying [L2] to the perfect pattern graph $P(\mathcal{B})$, choose a set $I\subseteq [t]$ with $\mathrm{\mid }I\mathrm{\mid }\ge \sqrt{t}$ that is either a clique or a stable set in $P(\mathcal{B})$.

If $I$ is a clique, then [L1] says that every two blocks indexed by $I$ are complete to one another, so $(B_i:i\in I)$ is a complete subblockade in the sense of [L3]. If $I$ is a stable set, then no two indices in $I$ are adjacent in the pattern graph, so every two corresponding blocks are anticomplete and $(B_i:i\in I)$ is an anticomplete subblockade. In either case the width is at least that of $\mathcal{B}$ by [L4].

Therefore $\mathcal{B}$ has a complete or anticomplete subblockade of length at least $\sqrt{t}$ and width at least the original width.

The first clause of [L1] already holds for $G$ by the hypothesis $\kappa (G)<\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$.

Let $H$ be a proper induced subgraph of $G$. Then [L2] makes $H$ $\mathcal{H}$-free, and $\mathrm{\mid }V(H)\mathrm{\mid }<\mathrm{\mid }V(G)\mathrm{\mid }$. By the minimality of $G$, the graph $H$ cannot satisfy $\kappa (H)<\mathrm{\mid }V(H){\mathrm{\mid }}^{\tau }$. Hence $\kappa (H)\ge \mathrm{\mid }V(H){\mathrm{\mid }}^{\tau }$.

Steps 1.1 and 1.2 are exactly the two clauses in [L1], so $G$ is $\tau$-critical.

We argue by induction on $t$. If $t=1$, then $V(\mathcal{B})=B_1$, so $\kappa (G[V(\mathcal{B})])=\kappa (G[B_1]),$ and the claim is immediate.

Assume now that $t>1$ and that the theorem is known for shorter pure blockades with cograph pattern. By [L2], the cograph $P$ is disconnected or its complement is disconnected. Choose either a connected component $I$ of $P$ in the first case, or an anticomponent $I$ of $P$ in the second case, and let $J:=[t]\setminus I$. Then $I$ and $J$ are nonempty. Put $U:={\bigcup }_{i\in I}{B}_i,W:={\bigcup }_{j\in J}{B}_j,V:=U\cup W=V(\mathcal{B})\mathrm{.}$

The induced pattern subgraphs $P[I]$ and $P[J]$ are cographs by [L1]. If $I$ is a component, then [L3] and [L4] make $U$ anticomplete to $W$; if $I$ is an anticomponent, then [L3] and [L4] make $U$ complete to $W$.

Applying the induction hypothesis to the subblockades indexed by $I$ and $J$ gives $\kappa (G[U])\ge {\sum }_{i\in I}\kappa (G[B_i]),\kappa (G[W])\ge {\sum }_{j\in J}\kappa (G[B_j])\mathrm{.}$

If $U$ is anticomplete to $W$, then a stable set in $G[U]$ together with a stable set in $G[W]$ is stable in $G[V]$, while every clique in $G[V]$ lies in one side. Thus $\alpha (G[V])\ge \alpha (G[U])+\alpha (G[W]),\omega (G[V])\ge \max \{\omega (G[U]),\omega (G[W])\},$ and [L5] yields $\kappa (G[V])\ge \kappa (G[U])+\kappa (G[W])$. If $U$ is complete to $W$, the same reasoning with cliques and stable sets exchanged again gives $\kappa (G[V])\ge \kappa (G[U])+\kappa (G[W])$.

Combining steps 3.1 and 3.2 gives $\kappa (G[V(\mathcal{B})])=\kappa (G[V])\ge {\sum }_{i=1}^t\kappa (G[B_i])\mathrm{.}$ Together with step 1.1, this closes the induction.

Suppose for contradiction that $\mathcal{B}=(B_1,\dots ,B_t)$ is a pure blockade in $G$ with cograph pattern, length $t$, width at least $\mathrm{\mid }V(G)\mathrm{\mid }{t}^{-1\mathrm{/}\tau }$, and each $B_i$ a proper subset of $V(G)$. By [L1], each proper induced subgraph $G[B_i]$ satisfies $\kappa (G[B_i])\ge \mathrm{\mid }{B}_i{\mathrm{\mid }}^{\tau }$. Since each block has size at least the width, [F1] gives $\mathrm{\mid }{B}_i\mathrm{\mid }\ge \mathrm{\mid }V(G)\mathrm{\mid }{t}^{-1\mathrm{/}\tau }>0$, so [L5] and [L4] yield $\kappa (G[B_i])\ge \mathrm{\mid }{B}_i{\mathrm{\mid }}^{\tau }\ge (\mathrm{\mid }V(G)\mathrm{\mid }{t}^{-1\mathrm{/}\tau }{)}^{\tau }=\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }{t}^{-1}$ for every $i$.

Let $X:=V(\mathcal{B})=B_1\cup \cdots \cup B_t$. Applying [L2] to the blockade and then using step 1.1 yields $\kappa (G[X])\ge {\sum }_{i=1}^t\kappa (G[B_i])\ge {\sum }_{i=1}^t\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }{t}^{-1}=\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }\mathrm{.}$ Then [L3] gives $\kappa (G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$, contradicting the first clause of [L1].

This contradiction proves that no such blockade exists.