Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths (Q2363116)

Summary: We prove that for all integers \(\kappa, s\geq 0\) there exists \(c\) with the following property. Let \(G\) be a graph with clique number at most \(\kappa\) and chromatic number more than \(c\). Then for every vertex-colouring (not necessarily optimal) of \(G\), some induced subgraph of \(G\) is an \(s\)-vertex path, and all its vertices have different colours. This extends a recent result of \textit{A. Gyárfás} and \textit{G. Sárközy} [Electron. J. Comb. 23, No. 4, Research Paper P4.46, 5 p. (2016)] who proved the same for graphs \(G\) with \(\kappa=2\) and girth at least five. For Part II see [\textit{M. Chudnovsky} et al., J. Comb. Theory, Ser. B 118, 109--128 (2016; Zbl 1332.05053)].