Erdős Problem #61

Round 4: reduction to prime graphs and a quantitative substitution barrier

1) ROUND-4 OBJECTIVE

Path (A): proof-direction. Round 3 already closed the next induced-path case $H=P_5$ and exhibited one explicit substitution obstruction using $C_5$. The most promising next step is therefore not to chase another isolated forbidden graph, but to isolate the true unresolved core of Problem 61 and to prove a general obstruction theorem that explains why the Round-3 construction is not accidental.

The new goal of this round is thus twofold:

1. prove that the full Erdős--Hajnal conjecture reduces to the case of prime graphs, using the substitution theorem of Alon--Pach--Solymosi; and
2. generalize the Round-3 $C_5$ blow-up obstruction from $H=P_5$ to every prime forbidden graph, obtaining a universal upper bound on any admissible Erdős--Hajnal exponent.

This is the most promising direction after Round 3 because it identifies exactly where the remaining difficulty lies, and it rules out an entire class of overly optimistic quantitative approaches.

2) ROUND-3 FOUNDATION USED

I rely explicitly on the following vetted Round-3 items.

• Round-3 Lemma 2 / Corollary 3: if $H$ is prime, then the class of $H$-free graphs is closed under vertex-substitution.
• Round-3 Lemma 4: for $G=B[F,\dots,F]$ with identical substituted blocks, \[ \alpha(G)=\alpha(B)\alpha(F),\qquad \omega(G)=\omega(B)\omega(F). \] In particular, repeated self-substitution multiplies both $\alpha$ and $\omega$.
• Round-3 Corollary 6: for $H=P_5$, the recursive family built from $C_5$ shows that the exponent $1/2$ from the cograph case cannot extend to all $P_5$-free graphs.

I do not reprove these results; I only generalize and reorganize them.

3) NEW INSIGHT / TOOL (ROUND-4)

There are two genuinely new ingredients in this round.

1. Prime-reduction theorem for Problem 61. Using the Alon--Pach--Solymosi substitution theorem together with a self-contained modular-decomposition lemma, I show that the full Erdős--Hajnal conjecture is equivalent to its restriction to prime graphs.

2. Universal substitution barrier. For a prime forbidden graph $H$, every smaller $H$-free graph $B$ generates by repeated self-substitution an infinite $H$-free family whose homogeneous-set exponent is exactly \[ \log_{|B|}\max\{\alpha(B),\omega(B)\}. \] Consequently, every admissible Erdős--Hajnal exponent for prime $H$ is bounded above by this quantity. Choosing $B=C_5$ recovers and vastly generalizes the Round-3 obstruction, while choosing a random-Ramsey base graph yields an asymptotic upper barrier \[ \delta_*(H)=O\!\left(\frac{\log\log |H|}{\log |H|}\right) \] for prime $H$.

4) ATTACK PLAN (ROUND-4)

Exact gap left after Round 3. Round 3 settled $H=P_5$ and exposed substitution as the mechanism behind the known upper-bound obstruction, but it did not determine whether that phenomenon was specific to $P_5$ or fundamental for the full conjecture.

Claims to prove now.

1. Every non-prime graph is a substitution of two strictly smaller graphs.
2. Therefore, by the Alon--Pach--Solymosi substitution theorem, proving Erdős--Hajnal for all prime graphs would settle Problem 61 completely.
3. For every prime graph $H$ and every $H$-free base graph $B$, the self-substitution tower $B^{(t)}$ stays $H$-free and has \[ |B^{(t)}|=|B|^t,\qquad \hom(B^{(t)})=\hom(B)^t, \] where $\hom(G):=\max\{\alpha(G),\omega(G)\}$.
4. Hence every admissible exponent for prime $H$ is at most $\log_{|B|}\hom(B)$.
5. Choosing $B=C_5$ gives a uniform barrier $\log_5 2$ for all prime $H$ with at least six vertices; choosing a random-Ramsey graph on $|H|-1$ vertices gives a stronger asymptotic barrier tending to $0$.

This plan overcomes the Round-3 obstacle because it turns one example into a general theorem and simultaneously isolates the exact core class (prime graphs) where new positive ideas are still required.

5) WORK (ROUND-4)

Notation.

For a graph $G$, let \[ \hom(G):=\max\{\alpha(G),\omega(G)\}. \] For a fixed graph $H$, define the best possible homogeneous-set exponent by \[ \delta_*(H):=\sup\left\{\delta>0: \text{every sufficiently large $H$-free graph $G$ satisfies }\hom(G)\ge |G|^{\delta}\right\}. \] Thus the Erdős--Hajnal conjecture for $H$ is exactly the assertion that $\delta_*(H)>0$.

A nonempty proper subset $M\subsetneq V(H)$ is a module of $H$ if every vertex of $V(H)\setminus M$ is either complete or anticomplete to $M$. A graph is prime if it has no module of size between $2$ and $|H|-1$.

If $B$ has vertices $1,\dots,m$ and $G_1,\dots,G_m$ are graphs, then \[ B[G_1,\dots,G_m] \] is the graph obtained by replacing vertex $i$ by the graph $G_i$, keeping all edges inside each $G_i$, and making every vertex of $G_i$ adjacent to every vertex of $G_j$ iff $ij\in E(B)$.

External theorem used (Alon--Pach--Solymosi).

If $H_1$ and $H_2$ have the Erdős--Hajnal property, and $H$ is obtained from $H_1$ by substituting $H_2$ for a vertex of $H_1$, then $H$ also has the Erdős--Hajnal property.

I use this theorem only in the qualitative reduction below; every quantitative upper bound proved afterwards is self-contained.

Lemma 1 (every non-prime graph is a substitution of smaller graphs).

Let $H$ be a non-prime graph. Then there exist graphs $H_1,H_2$ with \[ 2\le |H_2|<|H|,\qquad 2\le |H_1|<|H|, \] such that $H$ is obtained from $H_1$ by substituting $H_2$ for one vertex of $H_1$.

Proof. Since $H$ is non-prime, it has a nontrivial module $M\subsetneq V(H)$ with $2\le |M|\le |H|-1$. Let \[ H_2:=H[M]. \] Construct $H_1$ from $H$ by contracting $M$ to a single new vertex $m$:

• the vertex set of $H_1$ is $(V(H)\setminus M)\cup\{m\}$;
• two vertices outside $M$ are adjacent in $H_1$ exactly when they were adjacent in $H$;
• a vertex $x\in V(H)\setminus M$ is adjacent to $m$ in $H_1$ iff $x$ is adjacent to one (equivalently every) vertex of $M$ in $H$.

The definition is well-posed because $M$ is a module, so every outside vertex is either complete or anticomplete to $M$.

Now substitute $H_2$ for $m$ in $H_1$. Inside the substituted block we recover $H[M]$. Outside the block we keep exactly the adjacencies of $H\setminus M$. Between the block and the outside, a vertex $x\notin M$ is adjacent to every vertex of the block precisely when $x$ was complete to $M$ in $H$, and anticomplete otherwise. Therefore the resulting graph is exactly $H$.

Since $2\le |M|\le |H|-1$, we have $2\le |H_2|<|H|$. Also \[ |H_1|=|H|-|M|+1<|H|, \] and $|H_1|\ge 2$ because $M\neq V(H)$. Thus both factors are strictly smaller. $\square$

Corollary 2 (Problem 61 reduces to prime graphs).

Assume every prime graph has the Erdős--Hajnal property. Then every graph has the Erdős--Hajnal property. Equivalently, Problem 61 is solved once it is solved for prime graphs.

Proof. Proceed by induction on $|H|$. If $H$ is prime, there is nothing to prove. If $H$ is non-prime, Lemma 1 writes $H$ as a substitution of two strictly smaller graphs $H_1,H_2$. By induction, both $H_1$ and $H_2$ have the Erdős--Hajnal property. Applying the Alon--Pach--Solymosi theorem, $H$ also has the Erdős--Hajnal property. $\square$

Lemma 3 (universal substitution tower for prime forbidden graphs).

Let $H$ be prime, and let $B$ be an $H$-free graph with \[ b:=|B|\ge 2,\qquad r:=\hom(B). \] Define recursively \[ B^{(1)}:=B,\qquad B^{(t+1)}:=B[B^{(t)},\dots,B^{(t)}] \quad (t\ge 1), \] where there are $b$ copies of $B^{(t)}$ in the second display. Then for every $t\ge 1$:

1. $B^{(t)}$ is $H$-free;
2. $|B^{(t)}|=b^t$;
3. $\alpha(B^{(t)})=\alpha(B)^t$ and $\omega(B^{(t)})=\omega(B)^t$;
4. $\hom(B^{(t)})=r^t$.

Proof. We induct on $t$. The case $t=1$ is immediate. Assume the four statements hold for $t$.

Since $H$ is prime, Round-3 Lemma 2 (equivalently Round-3 Corollary 3) says that the class of $H$-free graphs is closed under substitution. The base graph $B$ is $H$-free, and by induction each block $B^{(t)}$ is $H$-free, so \[ B^{(t+1)}=B[B^{(t)},\dots,B^{(t)}] \] is also $H$-free. This proves $1$.

For the number of vertices, \[ |B^{(t+1)}|=|B|\cdot |B^{(t)}|=b\cdot b^t=b^{t+1}, \] proving $2$.

Now apply Round-3 Lemma 4 to the substitution with identical blocks: \[ \alpha(B^{(t+1)})=\alpha(B)\alpha(B^{(t)})=\alpha(B)^{t+1}, \] and similarly \[ \omega(B^{(t+1)})=\omega(B)\omega(B^{(t)})=\omega(B)^{t+1}. \] So $3$ holds. Finally, \[ \hom(B^{(t+1)})=\max\{\alpha(B)^{t+1},\omega(B)^{t+1}\}=\hom(B)^{t+1}=r^{t+1}, \] proving $4$. $\square$

Theorem 4 (general upper bound on admissible exponents for prime $H$).

Let $H$ be prime, and let $B$ be any $H$-free graph with $b:=|B|\ge 2$ and $r:=\hom(B)$. Then \[ \delta_*(H)\le \log_b r. \]

Proof. Fix any $\delta<\delta_*(H)$. By definition of $\delta_*(H)$, every sufficiently large $H$-free graph $G$ satisfies \[ \hom(G)\ge |G|^{\delta}. \] Apply this to the substitution tower $B^{(t)}$ from Lemma 3. For all sufficiently large $t$, \[ r^t=\hom(B^{(t)})\ge |B^{(t)}|^{\delta}=(b^t)^{\delta}=b^{t\delta}. \] Hence $r\ge b^{\delta}$, that is, \[ \delta\le \log_b r. \] Since this holds for every $\delta<\delta_*(H)$, we conclude \[ \delta_*(H)\le \log_b r. \] $\square$

Corollary 5 (Round-3 $C_5$ obstruction generalized to all larger prime graphs).

Let $H$ be prime with $|H|\ge 6$. Then \[ \delta_*(H)\le \log_5 2. \]

Proof. Take $B=C_5$. Then $|B|=5$ and $\hom(B)=2$. Because $|H|\ge 6$, the five-vertex graph $C_5$ is automatically $H$-free. Applying Theorem 4 gives \[ \delta_*(H)\le \log_5 2. \] $\square$

Lemma 6 (probabilistic base graph with logarithmic homogeneous number).

For every integer $n\ge 2$, there exists an $n$-vertex graph $R_n$ such that \[ \hom(R_n)\le 4\log_2 n +1. \]

Proof. Choose a random graph $G\sim G(n,1/2)$, and let \[ t:=\lceil 4\log_2 n\rceil. \] Let $X$ be the number of $t$-vertex subsets of $V(G)$ that induce either a clique or a stable set. For any fixed $t$-subset, the probability of being a clique is $2^{-\binom{t}{2}}$, and the same is true for being a stable set. Therefore \[ \mathbb E[X]=2\binom{n}{t}2^{-\binom{t}{2}}. \] Using $\binom{n}{t}\le n^t$ and writing $L:=\log_2 n$, we get \[ \mathbb E[X]\le 2^{1+tL-t(t-1)/2}. \] Now $t\ge 4L$ and $L\ge 1$. The function \[ f(x):=1+xL-\frac{x(x-1)}{2} \] is decreasing for $x\ge L+\tfrac12$, so in particular for $x\ge 4L$. Hence \[ 1+tL-\frac{t(t-1)}{2}\le 1+4L^2-\frac{(4L)(4L-1)}{2}=1-4L^2+2L\le -1. \] Thus $\mathbb E[X]<1$. So there exists a realization of $G$ with $X=0$, i.e. with no clique and no stable set of size $t$. For that graph, \[ \hom(G)\le t-1<4\log_2 n+1. \] Taking $R_n:=G$ proves the lemma. $\square$

Corollary 7 (asymptotic upper barrier for prime graphs).

Let $H$ be prime on $h\ge 3$ vertices. Then \[ \delta_*(H)\le \frac{\log\left(4\log_2(h-1)+1\right)}{\log(h-1)}. \] In particular, \[ \delta_*(H)=O\!\left(\frac{\log\log h}{\log h}\right) \qquad (h\to\infty) \] for prime graphs $H$.

Proof. Set $n:=h-1$. By Lemma 6 there exists an $n$-vertex graph $R_n$ with \[ \hom(R_n)\le 4\log_2 n+1. \] Since $|R_n|=h-1<|H|$, the graph $R_n$ is automatically $H$-free. Applying Theorem 4 with $B=R_n$ gives \[ \delta_*(H)\le \log_n\left(4\log_2 n+1\right)=\frac{\log\left(4\log_2(h-1)+1\right)}{\log(h-1)}. \] The asymptotic estimate follows immediately. $\square$

What this adds beyond Round 3.

Round 3 produced one explicit obstruction family for the special graph $H=P_5$. Round 4 shows that the same phenomenon is in fact universal for every prime forbidden graph: there is always a substitution tower witnessing an upper bound on the best possible exponent. Moreover, Corollary 2 isolates prime graphs as the exact unresolved core of Problem 61.

6) ADVERSARIAL VERIFICATION

• Does Lemma 1 really recover $H$ exactly? Yes. The only delicate point is the adjacency between the contracted module and the outside world. Because $M$ is a module, every outside vertex is either complete or anticomplete to $M$, so contracting $M$ to one vertex preserves precisely the data needed for substitution.

• Could Theorem 4 fail if the Erdős--Hajnal inequality only holds for sufficiently large graphs? No. The substitution tower $B^{(t)}$ has order $b^t\to\infty$, so eventually all members of the tower lie beyond the threshold in the definition of $\delta_*(H)$.

• Is primeness of $H$ really necessary in Lemma 3? Yes. The proof that $H$-free graphs are closed under substitution is exactly the Round-3 prime-forbidden lemma. Without primeness, substitution may create an induced copy of $H$ spread across several blocks.

• Could $\hom(B^{(t)})$ be smaller than $\hom(B)^t$ because cliques and stable sets interact asymmetrically? No. Round-3 Lemma 4 gives separate multiplicative formulas for $\alpha$ and $\omega$ under identical-block substitution. Taking the maximum afterwards yields $ \hom(B^{(t)})=\max\{\alpha(B)^t,\omega(B)^t\}=\hom(B)^t $ exactly.

• Is Corollary 5 genuinely stronger than the Round-3 $P_5$ obstruction? Yes. Round 3 proved the $C_5$ obstruction only for $H=P_5$. Corollary 5 proves the same numerical barrier for every prime graph with at least six vertices.

• Is Corollary 7 consistent with Corollary 5? Yes. Corollary 5 is a uniform finite-size barrier $\log_5 2\approx 0.4307$ valid for all prime $H$ with at least six vertices. Corollary 7 is weaker for small $h$ but stronger asymptotically, because its upper bound tends to $0$ as $h\to\infty$.

• Does Corollary 2 by itself solve Problem 61? No. It only reduces the conjecture to prime graphs. This is a genuine structural advance, but the prime case remains open in general.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 4 makes two strict advances beyond Round 3. First, it proves a precise reduction theorem: Problem 61 is equivalent to proving the Erdős--Hajnal conjecture for prime graphs only. Second, it proves a new universal obstruction theorem for prime forbidden graphs: every admissible exponent is bounded above by a substitution-based quantity, yielding in particular \[ \delta_*(H)\le \log_5 2\qquad \text{for all prime }H\text{ with }|H|\ge 6, \] and more generally \[ \delta_*(H)=O\!\left(\frac{\log\log |H|}{\log |H|}\right) \qquad \text{for prime }H. \] Thus the remaining difficulty is now sharply localized: one must prove positive exponents for prime graphs, but any successful general theory must also accommodate exponents that can decay to $0$ with $|H|$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 48%

9) REFERENCES

Only references actually used or checked in this round:

• P. Erdős and A. Hajnal, Ramsey-type theorems, Discrete Applied Mathematics 25 $1989$, 37--52.
• N. Alon, J. Pach, and J. Solymosi, Ramsey-type theorems with forbidden subgraphs, Combinatorica 21 $2001$, 155--170.
• M. Chudnovsky, The Erdős--Hajnal conjecture---a survey, Journal of Graph Theory 75 $2014$, 178--190.
• T. Nguyen, A. Scott, and P. Seymour, Induced subgraph density. IV. New graphs with the Erdős--Hajnal property, arXiv:2307.06455.
• T. Nguyen, A. Scott, and P. Seymour, Induced subgraph density. VII. The five-vertex path, arXiv:2312.15333; accepted for publication in Proceedings of the London Mathematical Society.

Erdős Problem #61: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

For every fixed graph $H$, does every $H$-free graph on $n$ vertices have a clique or independent set of size at least $n^{\delta(H)}$ for some $\delta(H)>0$?

All supplied versions considered: 61.tex. The source reduces to prime forbidden graphs using an external substitution theorem and obtains upper bounds from repeated identical substitution. I verify a further quantitative obstruction using alternating a graph and its complement; the argument below is conditional only on both bases being $H$-free.

2) WORK

Suppose $H$ is prime and both $B$ and $\overline B$ are $H$-free. Write $b=|B|$, $a=\alpha(B)$, $w=\omega(B)$. Form an alternating lexicographic product with $2t$ factors, $t$ copies of each. Then \[ |G_t|=b^{2t},\qquad \alpha(G_t)=\omega(G_t)=(aw)^t. \] For completeness, an independent set in $X[Y]$ meets an independent set of blocks of $X$ and takes at most $\alpha(Y)$ vertices in each; choosing maximum sets attains the product. The clique argument is identical. In the complement the two parameters exchange.

These products remain $H$-free: in an induced copy of a prime $H$, the intersection with any substituted block is a module; hence either the copy is wholly in a single block or it uses at most one vertex from each block. Either option would give an induced $H$ in one of the factors. It follows that any valid exponent satisfies \[ \delta(H)\le {\log(aw)\over2\log b}. \] This is at least as strong as $\log_b\max(a,w)$, and strictly stronger when $a\ne w$. The extra condition on $\overline B$ is automatic if $b<|H|$, and also when $H\cong\overline H$ and $B$ is $H$-free.

3) ADVERSARIAL VERIFICATION

If $H$ is not self-complementary and $b\ge|H|$, the complement need not be $H$-free, so the improvement cannot be used automatically. Multiplication concerns the separate clique and independence parameters, not their maximum at intermediate levels. This supplies upper obstructions, not the positive lower bound required by the conjecture.

4) FINAL

UNRESOLVED. The general prime forbidden-graph case remains unresolved. No new positive Erdős--Hajnal exponent is established here.

5) SOURCES CHECKED

No external theorem is used in the new argument. The supplied source was read in full; the saved Tao status snapshot is dated 2026-09-22.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 8%

Round 2: extending the structural method from $P_3$ to $P_4$

1) ROUND-2 OBJECTIVE

Path (A): proof-direction. The Round-1 output proved the Erdős--Hajnal conclusion for the special case $H=P_3$ by a full structural characterization (induced-$P_3$-free graphs are disjoint unions of cliques) plus a clique--independent product bound.

In Round 2 I push the same mechanism one notch further: I prove the conjectured polynomial conclusion for the next natural induced-path obstruction \[H=P_4,\] namely for induced-$P_4$-free graphs (cographs). This is a genuine strengthening beyond Round 1, and it stays aligned with the "structural decomposition $\Rightarrow$ product bound" strategy.

2) ROUND-1 FOUNDATION USED

I rely on the following vetted Round-1 items (no reproving):

• Round-1 Lemma 1: induced-$P_3$-free graphs are disjoint unions of cliques.
• Round-1 Lemma 2: for a disjoint union of cliques on $n$ vertices, $\alpha(G)\,\omega(G)\ge n$, hence $\max\{\alpha(G),\omega(G)\}\ge \sqrt n$.
• Round-1 "next moves" suggestion: treat induced-$P_4$-free graphs (cographs) via a structural characterization.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is the cograph (induced-$P_4$-free) decomposition:

Every induced-$P_4$-free graph is obtained from $K_1$ by repeatedly taking disjoint unions and joins.

Equivalently (Seinsche's theorem), every induced-$P_4$-free graph on at least two vertices is either disconnected, or its complement is disconnected.

The second new ingredient is a strengthening of Round-1 Lemma 2:

The product inequality $\alpha(G)\,\omega(G)\ge |V(G)|$ holds for all cographs, not just for disjoint unions of cliques.

The proof uses that this inequality is preserved by both disjoint union and join.

4) ATTACK PLAN (ROUND-2)

Round-1 gap addressed: Round 1 solved only $H=P_3$.

Claims to prove in Round 2:

1. (Structure) If $G$ is induced-$P_4$-free and connected with $|V(G)|\ge 2$, then $\overline G$ is disconnected. Equivalently, every induced-$P_4$-free graph is disconnected or co-disconnected.
2. (Closure + recursion) Induced-$P_4$-free graphs are exactly those built from $K_1$ by disjoint unions and joins.
3. (Quantitative bound) For every induced-$P_4$-free $G$ on $n$ vertices, $\alpha(G)\omega(G)\ge n$, hence $\max\{\alpha(G),\omega(G)\}\ge \sqrt n$. In particular, Erdős--Hajnal holds for $H=P_4$ with exponent $c(P_4)=\tfrac12$.

5) WORK (ROUND-2)

Notation.

$P_k$ denotes the path on $k$ vertices. A graph is $P_4$-free if it has no induced subgraph isomorphic to $P_4$. Write $G=G_1\uplus G_2$ for a disjoint union (no edges between parts) and $G=G_1*G_2$ for the join (add all edges between the parts).

Fact 0 (self-complementarity of $P_4$).

The complement of $P_4$ is isomorphic to $P_4$. Consequently, $G$ is $P_4$-free iff $\overline G$ is $P_4$-free.

Justification. Label $P_4$ as $1$--$2$--$3$--$4$. In $\overline{P_4}$ the edges are $13,14,24$, which form the path $3$--$1$--$4$--$2$. $\square$

Lemma 1 (Seinsche-type decomposition for $P_4$-free graphs).

Let $G$ be a connected $P_4$-free graph on $n\ge 2$ vertices. Then there exists a nontrivial partition $V(G)=A\cup B$ with $A,B\neq\emptyset$ such that every vertex of $A$ is adjacent to every vertex of $B$. In particular, $\overline G$ is disconnected.

Proof (induction on $n$). For $n\le 3$ this is a direct check: $K_2$, $P_3$, and $K_3$ each admit a nontrivial partition $A,B$ with all edges between $A$ and $B$.

Assume $n\ge 4$ and the statement holds for smaller connected $P_4$-free graphs. Fix a spanning tree $T$ of $G$, and let $x$ be a leaf of $T$ with neighbor $u$ in $T$. Then $G-x$ is connected. Since $G$ is $P_4$-free, so is the induced subgraph $G-x$. By the induction hypothesis applied to $G-x$, there is a partition \[V(G)\setminus\{x\}=A\cup B,\qquad A,B\neq\emptyset,\qquad \text{and } A\text{ is complete to }B.\] Without loss of generality, $u\in A$.

If $x$ is adjacent to every vertex of $B$, then $(A\cup\{x\},B)$ is the desired complete-join partition. So assume instead that $x$ has a non-neighbor $z\in B$. Define \[A_1:=A\cap N(x),\qquad A_0:=A\setminus A_1.\] Note that $u\in A_1$, hence $A_1\neq\emptyset$. If $A_0=\emptyset$, then $x$ is adjacent to all of $A$, and $(A,B\cup\{x\})$ is a complete-join partition. So assume $A_0\neq\emptyset$.

We claim that $A_1$ is complete to $A_0$. Indeed, take any $y\in A_1$ and any $w\in A_0$. We have

• $x$ is adjacent to $y$ (by definition of $A_1$),
• $y$ is adjacent to $z$ (since $y\in A$ and $z\in B$ and $A$ is complete to $B$),
• $z$ is adjacent to $w$ (since $w\in A$ and again $A$ is complete to $B$),
• $x$ is nonadjacent to $z$ (choice of $z\in B\setminus N(x)$),
• $x$ is nonadjacent to $w$ (since $w\in A_0=A\setminus N(x)$).

Thus, if $y$ were nonadjacent to $w$, the induced subgraph on $\{x,y,z,w\}$ would be exactly the path \[x-y-z-w,\] contradicting that $G$ is $P_4$-free. Hence $y$ must be adjacent to $w$ for all such choices, so $A_1$ is complete to $A_0$.

Now observe that every vertex of $A_1$ is adjacent to: (i) $x$ (by definition of $A_1$), (ii) $A_0$ (as just proved), and (iii) $B$ (since $A$ is complete to $B$). Therefore $A_1$ is complete to $V(G)\setminus A_1$. Taking the partition $(A_1,\,V(G)\setminus A_1)$ proves the lemma. $\square$

Corollary 2 (recursive description of $P_4$-free graphs).

A graph $G$ is $P_4$-free if and only if it can be generated from $K_1$ by repeatedly applying disjoint union $\uplus$ and join $*$.

Proof. The "if" direction: $P_4$-freeness is preserved under induced subgraphs, under disjoint union, and under join (a $P_4$ cannot use vertices from both sides of a join because that would create a vertex of degree $3$ in the induced subgraph). Also $K_1$ is $P_4$-free.

For the "only if" direction, proceed by induction on $n=|V(G)|$. If $n=1$, $G=K_1$. If $n\ge 2$ and $G$ is disconnected, write $G=G_1\uplus G_2$ with both parts nonempty (partition the components into two nonempty groups) and apply induction to each $G_i$. If $G$ is connected, apply Lemma 1 to obtain a nontrivial partition $V(G)=A\cup B$ such that $A$ is complete to $B$, i.e. $G=G[A]*G[B]$. Both induced subgraphs $G[A],G[B]$ are $P_4$-free and smaller, so induction applies. $\square$

Lemma 3 (clique/independence under $\uplus$ and $*$).

Let $G_1,G_2$ be graphs.

1. If $G=G_1\uplus G_2$, then \[\alpha(G)=\alpha(G_1)+\alpha(G_2),\qquad \omega(G)=\max\{\omega(G_1),\omega(G_2)\}.\]
2. If $G=G_1*G_2$, then \[\alpha(G)=\max\{\alpha(G_1),\alpha(G_2)\},\qquad \omega(G)=\omega(G_1)+\omega(G_2).\]

Proof. $1$ In a disjoint union, an independent set may be chosen independently in each component, while a clique must lie entirely within one component.

$2$ In a join, every vertex of $G_1$ is adjacent to every vertex of $G_2$, so cliques add across parts; an independent set cannot use vertices from both parts. $\square$

Lemma 4 (product bound for cographs).

If $G$ is $P_4$-free on $n$ vertices, then \[\alpha(G)\,\omega(G)\ge n.\] Consequently, $\max\{\alpha(G),\omega(G)\}\ge \sqrt n$.

Proof (induction on $n$ using Corollary 2). For $n=1$, $\alpha=\omega=1$. Assume $n\ge 2$ and the claim holds for smaller $P_4$-free graphs. By Corollary 2, write $G$ as either a disjoint union $G_1\uplus G_2$ or a join $G_1*G_2$ of two nonempty $P_4$-free graphs on $n_1,n_2$ vertices. By induction, $\alpha(G_i)\,\omega(G_i)\ge n_i$.

Disjoint union case. Using Lemma 3$1$, let $\omega(G)=\max\{\omega_1,\omega_2\}$ and wlog $\omega_1\ge \omega_2$. Then \[ \alpha(G)\omega(G)=(\alpha_1+\alpha_2)\omega_1\ge \alpha_1\omega_1+\alpha_2\omega_2\ge n_1+n_2=n. \]

Join case. Using Lemma 3$2$, let $\alpha(G)=\max\{\alpha_1,\alpha_2\}$ and wlog $\alpha_1\ge \alpha_2$. Then \[ \alpha(G)\omega(G)=\alpha_1(\omega_1+\omega_2)\ge \alpha_1\omega_1+\alpha_2\omega_2\ge n_1+n_2=n. \]

Finally, $\max\{\alpha,\omega\}\ge \sqrt{\alpha\omega}\ge \sqrt n$. $\square$

Proved special case (new in Round 2): $H=P_4$.

For $H=P_4$, the Erdős--Hajnal conclusion holds with exponent $c(P_4)=\tfrac12$: any induced-$P_4$-free graph $G$ on $n$ vertices has a clique or independent set of size at least $\sqrt n$.

Tightness.

The exponent $\tfrac12$ is best possible (up to rounding) even within cographs: if $n=m^2$, take $G$ to be the disjoint union of $m$ cliques of size $m$. Then $G$ is $P_4$-free (already induced-$P_3$-free by Round-1 Lemma 1), and \[\omega(G)=m,\qquad \alpha(G)=m,\qquad \max\{\alpha(G),\omega(G)\}=\sqrt n.\]

6) ADVERSARIAL VERIFICATION

• Base cases in Lemma 1. For $n\le 3$, connected graphs are $K_2,P_3,K_3$, and each has an explicit nontrivial complete-join partition.
• Induction step in Lemma 1. The spanning-tree leaf $x$ ensures $G-x$ is connected. The dichotomy "$x$ adjacent to all of $B$" or not is exhaustive; in the "not" case, the construction of $\{x,y,z,w\}$ uses $z\in B\setminus N(x)$ and $w\in A\setminus N(x)$, both ensured by the corresponding branches.
• Inducedness of the $P_4$ in Lemma 1. The only potentially problematic extra edge in the candidate path $x-y-z-w$ is $yw$; forcing $yw$ to be present is exactly what prevents the induced $P_4$, and yields the final join partition.
• Corollary 2 closure under join. Any four-vertex induced subgraph meeting both sides of a join has a vertex adjacent to all vertices on the other side, forcing degree $\ge 3$ in the induced subgraph, hence cannot be $P_4$.
• Product inequality algebra. In Lemma 4, the key inequalities are monotonicity: if $\omega_1\ge\omega_2$ then $\alpha_2\omega_1\ge\alpha_2\omega_2$, and if $\alpha_1\ge\alpha_2$ then $\alpha_1\omega_2\ge\alpha_2\omega_2$.
• Consistency with Round 1. Disjoint unions of cliques are cographs, and Lemma 4 reduces to Round-1 Lemma 2 in that subfamily; thus Round 2 strictly extends the Round-1 quantitative mechanism.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Beyond the Round-1 special case $H=P_3$, Round 2 proves the Erdős--Hajnal polynomial conclusion for the larger obstruction $H=P_4$ (cographs), with an explicit sharp exponent $c(P_4)=\tfrac12$. The full Erdős--Hajnal conjecture for general fixed $H$ remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 35%

9) REFERENCES

Only sources actually used/checked in Round 2:

• D. Seinsche, On a property of the class of $n$-colorable graphs, J. Combin. Theory Ser. B 16 $1974$, 191--193. (Classical source for the "$P_4$-free $\Rightarrow$ disconnected or co-disconnected" property.)
• M. G. S. Chung and D. B. West, Large $P_4$-free graphs with bounded degree, Journal of Graph Theory 17 $1993$, 109--116. (Contains a short inductive proof of Seinsche's property, used as a consistency check.)