Variants of the Gyárfás–Sumner conjecture: Oriented trees and rainbow paths.

Given a finite family ℱ ${\rm{ {\mathcal F} }}$ of graphs, we say that a graph G $G$ is “ℱ ${\rm{ {\mathcal F} }}$‐free” if G $G$ does not contain any graph in ℱ ${\rm{ {\mathcal F} }}$ as a subgraph. We abbreviate ℱ ${\rm{ {\mathcal F} }}$‐free to just “F $F$‐free” when ℱ={F} ${\rm{ {\mathcal F} }}=\{F\}$. A vertex‐colored graph H $H$ is called “rainbow” if no two vertices of H $H$ have the same color. Given an integer s $s$ and a finite family of graphs ℱ ${\rm{ {\mathcal F} }}$, let ℓ(s,ℱ) $\ell (s,{\rm{ {\mathcal F} }})$ denote the smallest integer such that any properly vertex‐colored ℱ ${\rm{ {\mathcal F} }}$‐free graph G $G$ having χ(G)≥ℓ(s,ℱ) $\chi (G)\ge \ell (s,{\rm{ {\mathcal F} }})$ contains an induced rainbow path on s $s$ vertices. Scott and Seymour showed that ℓ(s,K) $\ell (s,K)$ exists for every complete graph K $K$. A conjecture of N. R. Aravind states that ℓ(s,C3)=s $\ell (s,{C}_{3})=s$. The upper bound on ℓ(s,C3) $\ell (s,{C}_{3})$ that can be obtained using the methods of Scott and Seymour setting K=C3 $K={C}_{3}$ are, however, super‐exponential. Gyárfás and Sárközy showed that ℓ(s,{C3,C4})=O((2s)2s) $\ell (s,\{{C}_{3},{C}_{4}\})={\mathscr{O}}({(2s)}^{2s})$. For r≥2 $r\ge 2$, we show that ℓ(s,K2,r)≤(r−1)(s−1)(s−2)∕2+s $\ell (s,{K}_{2,r})\le (r-1)(s-1)(s-2)\unicode{x02215}2+s$ and therefore, ℓ(s,C4)≤s2−s+22 $\ell (s,{C}_{4})\,\le \,\frac{{s}^{2}-s+2}{2}$. This significantly improves Gyárfás and Sárközy's bound and also covers a bigger class of graphs. We adapt our proof to achieve much stronger upper bounds for graphs of higher girth: we prove that ℓ(s,{C3,C4,…,Cg−1})≤s1+4g−4 $\ell (s,\{{C}_{3},{C}_{4},\ldots ,{C}_{g-1}\})\le {s}^{1+\frac{4}{g-4}}$, where g≥5 $g\ge 5$. Moreover, in each case, our results imply the existence of at least s!∕2 $s!\unicode{x02215}2$ distinct induced rainbow paths on s $s$ vertices. Along the way, we obtain some new results on an oriented variant of the Gyárfás–Sumner conjecture. For r≥2 $r\ge 2$, let ℬr ${{\rm{ {\mathcal B} }}}_{r}$ denote the orientations of K2,r ${K}_{2,r}$ in which one vertex has out‐degree or in‐degree r $r$. We show that every ℬr ${{\rm{ {\mathcal B} }}}_{r}$‐free oriented graph having a chromatic number at least (r−1)(s−1)(s−2)+2s+1 $(r-1)(s-1)(s-2)+2s+1$ and every bikernel‐perfect oriented graph with girth g≥5 $g\ge 5$ having a chromatic number at least 2s1+4g−4 $2{s}^{1+\frac{4}{g-4}}$ contains every oriented tree on at most s $s$ vertices as an induced subgraph. [ABSTRACT FROM AUTHOR]