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

Given a finite family ℱ of graphs, we say that a graph G is "ℱ‐free" if G does not contain any graph in ℱ as a subgraph. We abbreviate ℱ‐free to just "F‐free" when ℱ={F}. 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 ℱ, let ℓ(s,ℱ) denote the smallest integer such that any properly vertex‐colored ℱ‐free graph G having χ(G)≥ℓ(s,ℱ) contains an induced rainbow path on s vertices. Scott and Seymour showed that ℓ(s,K) exists for every complete graph K. A conjecture of N. R. Aravind states that ℓ(s,C3)=s. The upper bound on ℓ(s,C3) that can be obtained using the methods of Scott and Seymour setting K=C3 are, however, super‐exponential. Gyárfás and Sárközy showed that ℓ(s,{C3,C4})=O((2s)2s). For r≥2, we show that ℓ(s,K2,r)≤(r−1)(s−1)(s−2)∕2+s and therefore, ℓ(s,C4)≤s2−s+22. 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, where g≥5. Moreover, in each case, our results imply the existence of at least s!∕2 distinct induced rainbow paths on s vertices. Along the way, we obtain some new results on an oriented variant of the Gyárfás–Sumner conjecture. For r≥2, let ℬr denote the orientations of K2,r in which one vertex has out‐degree or in‐degree r. We show that every ℬr‐free oriented graph having a chromatic number at least (r−1)(s−1)(s−2)+2s+1 and every bikernel‐perfect oriented graph with girth g≥5 having a chromatic number at least 2s1+4g−4 contains every oriented tree on at most s vertices as an induced subgraph. [ABSTRACT FROM AUTHOR]