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

Abstract

Given a triangle-free graph $G$ with chromatic number $k$ and a proper vertex coloring $\ddot{I}•$ of $G$, it is conjectured that $G$ contains an induced rainbow path on $k$ vertices under $\ddot{I}•$. Scott and Seymour proved the existence of an induced rainbow path on $(\log \log \log k{)}^{\frac{1}{3}-o(1)}$ vertices. We improve this to $(\log k{)}^{\frac{1}{2}-o(1)}$ vertices. Further, we prove the existence of an induced path that sees $\frac{k}{2}$ colors.

6 pages