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 and Rogers Mathew. It is available at https://arxiv.org/abs/2601.00602