Induced colorful trees and paths in large chromatic graphs (Q504985)

Summary: In a proper vertex coloring of a graph a subgraph is colorful if its vertices are colored with different colors. It is well-known that in every proper coloring of a \(k\)-chromatic graph there is a colorful path \(P_k\) on \(k\) vertices. The first author proved in [Zastosow. Mat. 19, No. 3--4, 413--441 (1987; Zbl 0718.05041)] that \(k\)-chromatic and triangle-free graphs have a path \(P_k\) which is an induced subgraph. N. R. Aravind conjectured that these results can be put together: in every proper coloring of a \(k\)-chromatic triangle-free graph, there is an induced colorful \(P_k\). Here we prove the following weaker result providing some evidence towards this conjecture: For a suitable function \(f(k)\), in any proper coloring of an \(f(k)\)-chromatic graph of girth at least five, there is an induced colorful path on \(k\) vertices.