Variants of the Gyàrfàs-Sumner Conjecture: Oriented Trees and Rainbow Paths
share
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. A vertex-coloured graph H is called "rainbow" if no two vertices of H have the same colour. Given an integer s and a finite family of graphs ℱ, let ℓ(s,ℱ) denote the smallest integer such that any properly vertex-coloured ℱ-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,C_3)=s. The upper bound on ℓ(s,C_3) that can be obtained using the methods of Scott and Seymour setting K=C_3 are, however, super-exponential. Gyàrfàs and Sàrközy showed that ℓ(s,{C_3,C_4})=𝒪((2s)^2s). We show that ℓ(s,K_2,r)≤ (r-1)(s-1)s/2+s and therefore, ℓ(s,C_4)≤s^2+s/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,{C_3,C_4,…,C_g-1})≤ s^1+4/g-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. Let ℬ_r denote the orientations of K_2,r in which one vertex has out-degree r. We show that every ℬ_r-free oriented graph having chromatic number at least (r-1)(s-1)(s-2)+s and every bikernel-perfect oriented graph with girth g≥ 5 having chromatic number at least 2s^1+4/g-4 contains every oriented tree on at most s vertices as an induced subgraph.
READ FULL TEXT