Towards a conjecture on long induced rainbow paths in triangle-free graphs

Given a triangle-free graph G with chromatic number k and a proper vertex coloring \phi of G, it is conjectured that G contains an induced rainbow path on k vertices under \phi.

Scott and Seymour proved the existence of an induced rainbow path on (log log log k)^{1/3-o(1)} vertices. We improve this bound to (log k)^{1/2-o(1)}. Further, we prove the existence of an induced path that sees k/2 colors.

This is joint work with N.R. Aravind. It is available at
https://arxiv.org/abs/2601.00602