EUROPEAN JOURNAL OF COMBINATORICS
© 2017, Australian National University. All rights reserved. We prove that for all integers k, s ≥ 0 there exists c with the following property. Let G be a graph with clique number at most k 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 Gyárfás and Sárközy (2016), who proved the same for graphs G with k = 2 and girth at least five.
Submitted to ORA: