Variants of the Gy\`arf\`as-Sumner Conjecture: Oriented Trees and Rainbow Paths

Given a finite family $\mathcal{F}$ of graphs, we say that a graph $G$ is “$\mathcal{F}$-free” if $G$ does not contain any graph in $\mathcal{F}$ as a subgraph. A vertex-colored graph $H$ is called “rainbow” if no two vertices of $H$ have the same color. Given an integer $s$ and a finite family of graphs $\mathcal{F}$, let $\mathrm{\ell }(s,\mathcal{F})$ denote the smallest integer such that any properly vertex-colored $\mathcal{F}$-free graph $G$ having $\chi (G)\ge \mathrm{\ell }(s,\mathcal{F})$ contains an induced rainbow path on $s$ vertices. Scott and Seymour showed that $\mathrm{\ell }(s,K)$ exists for every complete graph $K$. A conjecture of N. R. Aravind states that $\mathrm{\ell }(s,C_3)=s$. The upper bound on $\mathrm{\ell }(s,C_3)$ that can be obtained using the methods of Scott and Seymour setting $K=C_3$ are, however, super-exponential. Gy'arf'as and S'ark"ozy showed that $\mathrm{\ell }(s,\{C_3,C_4\})=\mathcal{O}((2s{)}^{2s})$. For $r\ge 2$, we show that $\mathrm{\ell }(s,K_{2,r})\le (r-1)(s-1)(s-2)\mathrm{/}2+s$ and therefore, $\mathrm{\ell }(s,C_4)\le \frac{s^2-s+2}{2}$. This significantly improves Gy'arf'as and S'ark"ozy’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 $\ell(s,{C_3,C_4,\ldots,C_{g-1}})\leq s^{1+\frac{4}{g-4}}$,where$g\geq 5$. Moreover, in each case, our results imply the existence of at least $s!\mathrm{/}2$ distinct induced rainbow paths on $s$ vertices. Along the way, we obtain some results on related problems on oriented graphs. For $r\ge 2$, let ${\mathcal{B}}_r$ denote the orientations of $K_{2,r}$ in which one vertex has out-degree or in-degree $r$. We show that every ${\mathcal{B}}_r$-free oriented graph $G$ having $\chi(G)\geq (r-1)(s-1)(s-2)+2s+1$andeverybikernel-perfectorientedgraph$G$withgirth$g\geq 5$having$\chi(G)\geq 2s^{1+\frac{4}{g-4}}$containsevery$s$ vertex oriented tree as an induced subgraph.