We prove that for all integers $\kappa, s\ge 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 Gyárfás and Sárközy (2016) who proved the same for graphs $G$ with $\kappa=2$ and girth at least five.
@article{10_37236_6768,
author = {Alex Scott and Paul Seymour},
title = {Induced subgraphs of graphs with large chromatic number. {IX:} {Rainbow} paths},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {2},
doi = {10.37236/6768},
zbl = {1366.05047},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6768/}
}
TY - JOUR
AU - Alex Scott
AU - Paul Seymour
TI - Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/6768/
DO - 10.37236/6768
ID - 10_37236_6768
ER -
%0 Journal Article
%A Alex Scott
%A Paul Seymour
%T Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6768/
%R 10.37236/6768
%F 10_37236_6768
Alex Scott; Paul Seymour. Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths. The electronic journal of combinatorics, Tome 24 (2017) no. 2. doi: 10.37236/6768
