September 14, 2017 um 1:00 pm – 11:59 pm
Saarbrücken building E1 4
room 024
Davis Issac

Given a graph G = (V, E) whose vertices have been properly coloured, we say
that a path in G is colourful if no two vertices in the path have the same
colour. It is a corollary of the Gallai-Roy Theorem that every properly
coloured graph contains a colourful path on chi(G) vertices, where chi(G) is
the chromatic number of G. We explore a conjecture that states that every
properly coloured triangle-free graph G contains an induced colourful path on
chi(G) vertices.