On polynomially high-chromatic pure pairs

Abstract

Let $T$ be a forest. We study polynomially high-chromatic pure pairs in graphs with no $T$ as an induced subgraph ($T$-free graphs in other words), with applications to the polynomial Gyárfás-Sumner conjecture. In addition to reproving several known results in the literature, we deduce: $\bullet$ If $T=P_5$ is the five-vertex path, then every $T$-free graph $G$ with clique number $w\ge 2$ contains a complete pair $(A,B)$ of induced subgraphs with $\ddot{I}‡(A)\ge w^{-d}\ddot{I}‡(G)$ and $\ddot{I}‡(B)\ge 2^{-d}\ddot{I}‡(G)$, for some universal $d\ge 1$. The proof uses the recent Erdős-Hajnal result for $P_5$-free graphs. Via the classical Gyárfás path argument, such a ``polynomial versus linear high-$\ddot{I}‡$ complete pairs'' result can be viewed as further supporting evidence for the polynomial Gyárfás-Sumner conjecture for $P_5$. In particular, it implies \[χ(G)\le w^{O(\log w/\log\log w)}\] which asymptotically improves the bound $\ddot{I}‡(G)\le w^{\log w}$ of Scott, Seymour, and Spirkl. $\bullet$ If $T$ and a broom satisfy the polynomial Gyárfás-Sumner conjecture, then so does their disjoint union. Unifying earlier results of Chudnovsky, Scott, Seymour, and Spirkl, and of Scott, Seymour, and Spirkl, this gives new instances of $T$ for which the conjecture holds.

24 pages, not intended for publication due to arXiv:2512.24907